Тривимірна комп`ютерна графіка

Введення

Машинна графіка в даний час вже цілком сформувалася як наука. Існує апаратне і програмне забезпечення для отримання різноманітних зображень - від простих креслень до реалістичних образів природних об'єктів. Машинна графіка використовується майже у всіх наукових та інженерних дисциплінах для наочності сприйняття і передачі інформації. Знання її основ нашого часу необхідно кожному вченому або інженеру. Машинна графіка владно вторгається в бізнес, медицину, рекламу, індустрію розваг. Застосування під час ділових нарад демонстраційних слайдів, підготовлених методами машинної графіки та інші засобам автоматизації конторського праці, вважається нормою. У медицині стає звичайною отримання тривимірних зображень внутрішніх органів за даними комп'ютерних томографів. У наші дні телебачення та інші рекламні підприємства часто вдаються до послуг машинної графіки та комп'ютерної мультиплікації. Використання машинної графіки в індустрії розваг охоплює такі несхожі області як відеоігри і повнометражні художні фільми.

На сьогоднішній день створено велику кількість програм, що дозволяють створювати і редагувати тривимірні сцени та об'єкти. Серед найбільш популярних можна назвати такі як 3D studio Max, яка дозволяє тривимірні комп'ютерні ролики. Область її застосування в основному реклама, мультиплікація й телевізійних передач. Інший не менш популярний пакет програм це Auto-CAD. Він застосовується в основному інженерами і проектувальниками для створення креслень і просторових моделей. Крім цих існує безліч інших спеціалізованих програмних пакетів охоплюють практично всі сторони людського життя.

Серед різноманіття можливостей, що надаються сучасними обчислювальними засобами, ті, що засновані на просторово-образному мисленні людини, займають особливе місце. Сучасні програмно-оперативні засоби комп'ютерної графіки є дуже ефективний інструмент підтримки такого мислення при виконанні робіт найрізноманітніших видів. З іншого боку саме просторово-образне мислення є неформальною творчої основою для розширення образотворчих можливостей комп'ютерів. Це важлива обставина передбачає взаємно збагачує співробітництво дедалі більш досконалої техніки і людини з усім багатством знання, накопиченого попередніми поколіннями. Око і раніше був ефективним засобом пізнання людиною світу і себе. Тому настільки привабливою виявляється комп'ютерна візуалізація, особливо візуалізація динамічна, яку слід розглядати як найважливіший інструмент для вивчення наук.

Введення в машинну графіку

Сучасна машинна графіка - це ретельно розроблена дисципліна. Грунтовно досліджені сегменти геометричних перетворень і описів кривих і поверхонь. Також вивчено, але все ще продовжують розвиватися методи растрового сканування, відсікання, видалення ліній і поверхонь, колір, зафарбування, текстура і ефекти прозорості. Зараз найбільший інтерес представляють саме ці розділи машинної графіки.

Машинна графіка - складна і різноманітна дисципліна. Для вивчення її, перш за все, необхідно розбити на доступні для огляду частини. Перш за все необхідно розглянути методи та алгоритми растрової графіки. Це досить простий, але дуже важливий розділ машинної графіки. У цьому розділі розглядаються алгоритми малювання відрізків і кіл на екрані монітора, методи растрової розгортки, заповнення багатокутників, усунення ступінчастості або сходового ефекту. Окремо слід розглянути методи відсікання зображення, тобто відбору інформації, яка необхідна для візуалізації конкретної сцени.

При побудові тривимірної сцени виникає проблема видалення невидимих ​​ліній і поверхонь. Це одна з найбільш складних складових візуалізації тривимірних об'єктів. Способи досягнення ефектів прозорості, відблиски і т.п., строго кажучи, не входить у завдання видалення невидимих ​​частин тривимірних об'єктів і, тим не менш, деякі з них тісно пов'язані з цією проблемою. Наприклад, побудова тіней. Не дивлячись на це, в комп'ютерній графіці виділяється досить великий розділ, присвячений побудові реалістичних зображень, в якому детально розглядаються методи створення таких ефектів як дзеркальне відображення, заломлення променів у різних середовищах, тіні, фактура об'єкта. Також розглядаються різні джерела світла, їх спектральні характеристики і форма. Сюди ж відносяться колірні ефекти, згладжування поверхонь і багато іншого.

Як видно з вище сказаного комп'ютерна графіка це досить об'ємна дисципліна, тому я зупинюся лише на деяких її найбільш цікавих аспектах.

Растрова графіка

Будь-яке зображення, в тому числі і тривимірне, складається з графічних примітивів. Тому, перш за все, необхідно знати спеціальні методи генерації зображення, креслення прямих і кривих ліній, зафарбування багатокутників, що створює враження суцільних об'єктів. Розглянемо деякі з цих методів.

Алгоритми креслення відрізків

Оскільки екран дисплея можна розглядати як матрицю дискретних елементів (пікселів), кожен з яких може бути підсвічений, не можна безпосередньо провести відрізок з однієї точки в іншу. Процес визначення пікселів, найкращим чином апроксимуючих заданий відрізок, називається розкладом в растр. Для горизонтальних, вертикальних і нахилених під кутом 45 ° відрізків вибір растрових елементів очевидний. При будь-якій іншій орієнтації вибрати потрібні пікселі важче.

Існує декілька алгоритмів виконують це завдання. Розглянемо два з них.

Цифровий диференціальний аналізатор

Один з методів розкладання відрізка в растр полягає у вирішенні диференціального рівняння, що описує цей процес. Для прямої лінії маємо:

або н

Рішення представляється у вигляді

де x1, y1 і x2, y2 - кінці розкладаного відрізка і yi - початкове значення для чергового кроку вздовж відрізка. Фактично рівняння (2.1.) Представляє собою рекурентне співвідношення для послідовних значень y вздовж потрібного відрізка. Цей метод, використовуваний для розкладання в растр відрізків, називається цифровим диференціальним аналізатором (ЦДА). У простому ЦДА або , Або (Більше з збільшень) вибирається в якості одиниці растра. Нижче наводиться простий алгоритм, що працює у всіх квадрантах:

Процедура розкладання в растр відрізка методом цифрового диференціального аналізатора (ЦДА)

передбачається, що кінці відрізка (x1, y1) та (x2, y2) не збігаються

Integer - функція перетворення дійсного числа в ціле.

Примітка: у багатьох реалізаціях функція Integer означає взяття цілої частини, тобто Integer (- 8.5) = - 9, а не - 8. В алгоритмі використовується саме така функція.

Sign - функція, що повертає - 1, 0, 1 для негативного нульового і позитивний аргумент відповідно.

if abs (x2 - x1) ³ abs (y2 - y1) then

Довжина = abs (x2 - x1)

else

Довжина = abs (y2 - y1)

end if

вважаємо більше з збільшень D x або D y рівним одиниці растра

D x = (x2 - x1) / Довжина

D y = (y2 - y1) / Довжина

округляємо величини, а не відкидаємо дробову частину

використання знакової функції робить алгоритм придатним для всіх квадрантів

x = x1 + 0.5 * Sign (D x)

y = y1 + 0.5 * Sign (D y)

початок основного циклу

i = 1

while (i £ Довжина)

Plot (Integer (x), Integer (y))

x = x + D x

y = y + D y

i = i + 1

end while

finish

За допомогою цього алгоритму отримують прямі, цілком задовільного вигляду, але у нього є ряд недоліків. По-перше, погана точність в кінцевих точках. По-друге, результати роботи алгоритму залежить від орієнтації відрізка. До того ж запропонований алгоритм використовує речову арифметику, що помітно знижує швидкість виконання.

Алгоритм Брезенхема

Алгоритм Брезенхема вибирає оптимальні растрові координати для подання відрізка. У процесі роботи одна з координат - або x, або в (в залежності від кутового коефіцієнта) - змінюється на одиницю. Зміна інший координати (або на нуль, або на одиницю) залежить від відстані між дійсним станом відрізка і найближчими координатами сітки. Таку відстань називається помилкою.

Алгоритм побудований так, що потрібно перевіряти лише знак цієї помилки. На рис.2.1 це ілюструється для відрізка в першому

½ £ D y £ 1 (помилка ³ 0)

0 £ D y / D x <½ (помилка D x then

Брешемо = D x

D x = D y

D y = Брешемо

Обмін = 1

else

Обмін = 0

end if

ініціалізація з поправкою на половину пікселя

= 2 * D y - D x

основний цикл

for i = 1 to D x

Plot (x, y)

While ( ³ 0)

If Обмін = 1 then

x = x + s1

else

y = y + s2

end if

= - 2 * D x

end while

if Обмін = 1 then

y = y + s2

else

x = x + s1

end if

= + 2 * D y

next i

finish

Цей алгоритм задовольняє самим суворим вимогам. Він має прийнятну швидкість і може бути легко реалізований на апаратному або мікропрограмному рівні.

Алгоритм Брезенхема для генерації кіл

У растр потрібно розкладати як лінійні, але й інші, більш складні функції. Розкладання конічних перерізів, тобто кіл, еліпсів, парабол, гіпербол присвячено значну кількість робіт. Найбільшу увагу, зрозуміло, приділено окружності. Один з найбільш ефективних і простих для розуміння алгоритмів генерації окружності належить

2.3 Генерація повної окружності з дуги в першому Октант

Брезенхему. Для початку зауважимо, що необхідно згенерувати тільки одну восьму частину кола. Решта її частини можна отримати послідовними відображеннями, як це показано на рис. 2.3. Якщо сгенерирован перший октант (від 0 ° до 45 ° проти годинникової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої у = x, що дає разом перший квадрант. Перший квадрант відбивається щодо прямої x = 0 для отримання відповідної частини окружності у другому квадраті. Верхня півколо відбивається відносно прямої у = 0 завершення побудови. На рис.2.3. наведено двомірні матриці відповідних перетворень.

Для виведення алгоритму розглянемо першу чверть кола з центром у початку координат. Зауважимо, що якщо робота алгоритму починається в точці x = 0, у = R, то при генерації окружності за годинниковою стрілкою в першому квадраті у є монотонно спадною функцією аргументу x (рис. 2.4). Аналогічно, якщо вихідною точкою є y = 0, x = R, то при генерації окружності проти годинникової стрілки x буде монотонно спадною функцією аргументу у. У нашому випадку вибирається генерація за годинниковою стрілкою з початком у точці x = 0, у = R. Передбачається, що центр кола та початкова точка перебувають точно в точках растру.

Для будь-якої заданої точки на колі при генерації за годинниковою стрілкою існує тільки три можливості вибрати наступний піксел, найкращим чином наближує окружність: горизонтально вправо, по діагоналі вниз і вправо, вертикально вниз. На рис.2.5 цих напрямів є такі відповідно mH, mD, mV.

2.4 Окружність у першому квадранті. 2.5 Вибір пікселів в першому квадранті

Алгоритм вибирає піксель, для якого мінімальний квадрат відстані між одним з цих пікселів і колом, тобто щонайменше з

mH = | (xi + 1) 2 + (yi) 2 - R2 |

mH = | (xi + 1) 2 + (yi - 1) 2 - R2 |

mH = | (xi) 2 + (yi - 1) 2 - R2 |

Обчислення можна спростити, якщо зауважити, що в околі точки (xi, yi) можливі тільки п'ять типів перетинань кола та сітки растра, наведених на рис.2.6.

Різниця між квадратами відстаней від центру кола до діагонального піксела (xi + 1, yi - 1) і від центру до точки на колі R2 дорівнює

Як і в алгоритмі Брезенхема для відрізка, для вибору відповідного пікселя бажано використовувати тільки знак помилки, а не її величину.

2.6 Перетин кола і сітки растра

При D <0 діагональна точка (xi + 1, yi - 1) перебуває усередині реальної колу, тобто це випадки 1 або 2 на рис.2.6. Ясно, що в цій ситуації слід вибрати або піксел (xi + 1, yi) тобто mH, або піксел (xi + 1, yi - 1), тобто mD. Для цього спочатку розглянемо випадок 1 і перевіримо різницю квадратів відстаней від окружності до пікселів в горизонтальному і діагональному напрямках:

При d <0 відстань від кола до діагонального піксела

(MD) більше, ніж до горизонтального (mH). Навпаки, якщо d> 0, відстань до горизонтального піксела (mH) більше. Таким чином,

при d <0 вибираємо mH (xi + 1, уi)

при d> 0 вибираємо mD (xi + 1, уi - 1)

При d = 0, коли відстані від кола до обох пікселів однакові, вибираємо горизонтальний крок.

Кількість обчислень, необхідних для оцінки величини d, можна скоротити, якщо зауважити, що у випадку 1

так як діагональний піксел (xi + 1, уi - 1) завжди лежить всередині кола, а горизонтальний (xi + 1, уi) - поза нею. Таким чином, d можна обчислити за формулою

Доповнення до квадрата члена (yi) 2 з допомогою додавання і віднімання - 2уi + 1 дає

У квадратних дужках стоїть з визначення D i, і його підстановка

d = 2 (D i + yi) - 1

істотно спрощує вираз.

Розглянемо випадок 2 на рис.2.6 зауважимо, що тут має бути обраний горизонтальний піксел (xi + 1, уi), тому що в є монотонно спадною функцією. Перевірка компонент d показує, що

оскільки у разі 2 горизонтальний (xi + 1, уi) і діагональний (xi + 1, уi - 1) пікселі лежать всередині окружності. Отже, d <0, і при використанні того самого критерію, що і у випадку 1, вибирається піксел (xi + 1, уi).

Якщо D i> 0, то діагональна точка (xi + 1, уi - 1) знаходиться поза колу, тобто це випадки З і 4 на рис.2.6. У даній ситуації ясно, що повинен бути обраний або піксел (xi + 1, уi - 1), тобто mD, або (xi, уi - 1), тобто mV. Аналогічно розбору попереднього випадку критерій вибору можна отримати, розглядаючи спочатку випадок З і перевіряючи різницю між квадратами відстаней від кола до діагонального mD і вертикального mV пікселів, тобто

При d <0 відстань від кола до вертикального піксела (xi, уi - 1) більше й слід вибрати діагональний крок mD, до пикселу (xi + 1, уi - 1). Навпаки, у разі d> 0 відстань від кола до діагонального піксела більше й слід вибрати вертикальний рух до пикселу (xi, уi - 1). Таким чином,

при d £ 0 вибираємо mD в (xi + 1, уi - 1)

при d <0 вибираємо mV в (xi, уi - 1)

Тут у випадку d = 0, тобто коли відстані рівні, обраний діагональний крок.

Перевірка компонент d показує, що

оскільки для випадку З діагональний піксел (xi + 1, уi - 1) знаходиться поза кола, тоді як вертикальний піксел (xi, уi - 1) лежить всередині її. Це дозволяє записати d у вигляді

Доповнення до квадрата члена (xi) 2 з допомогою додавання і віднімання 2xi + 1 дає

Використання визначення D i призводить вираз до виду

Тепер, розглядаючи випадок 4, знову зауважимо, що слід вибрати вертикальний піксел (xi, уi - 1), так як y є монотонно спадною функцією при зростанні x. перевірка компонент d для випадку 4 показує, що

оскільки обидва піксела знаходяться поза кола. Отже, d> 0 і при використанні критерію, розробленого для випадку 3, відбувається вірний вибір mV.

Залишилося перевірити тільки випадок 5 на рис.2.7, який зустрічається, коли діагональний піксел (xi + 1, уi - 1) лежить на колі, тобто D i = 0. Перевірка компонент d показує, що

Отже, d> 0 і вибирається діагональний піксел (xi + 1, уi - 1). Аналогічним чином оцінюємо компоненти d:

і d <0, що є умовою вибору правильного діагонального кроку до (хi + 1, уi - 1). Таким чином, випадок D i = 0 підпорядковується тому ж критерію, як і випадок D i <0 або D i> 0.

Підіб'ємо підсумок отриманих результатів:

D i <0

d £ 0 вибираємо піксел (хi + 1, уi) ® mH

d> 0 вибираємо піксел (хi + 1, уi - 1) ® mD

D i> 0

d £ 0 вибираємо піксел (хi + 1, уi - 1) ® mD

d> 0 вибираємо піксел (хi, уi - 1) ® mV

D i = 0 вибираємо піксел (хi + 1, уi - 1) ® mD

Легко розробити прості рекурентні співвідношення дня реалізації покрокового алгоритму. Спочатку розглянемо горизонтальний крок mH до пикселу (хi + 1, уi). Позначимо це нове положення піксела як (i + 1). Тоді координати нового піксела і значення D i рівні

Аналогічно координати нового піксела і значення D i для кроку mD до пикселу (хi + 1, уi - 1) такі:

Те ж саме для кроку mV до (хi, уi - 1)

Реалізація алгоритму Брезенхема для кола наводитися нижче.

Покроковий алгоритм Брезенхема для генерації окружності у першому квадранті

всі змінні цілі

xi = 0

yi = R

D i = 2 (1 - R)

Межа = 0

Plot (xi, yi)

if yi £ Межа then 4

виділення випадку 1 або 2, 4 або 5, або 3

if D i <0 then 2

if D i> 0 then 3

if D i = 0 then 20

визначення випадку 1 або 2

d = 2D i + 2yi - 1

if d £ 0 then 10

if d> 0 then 20

визначення випадку 4 або 5

d = 2D i + 2xi - 1

if d £ 0 then 20

if d> 0 then 30

виконання кроків

крок mH

xi = xi +1

D i = D i +2 xi + 1

goto 1

крок mD

xi = xi +1

yi = yi - 1

D i = D i +2 xi - 2yi + 2

goto 1

крок mV

30yi = yi - 1

D i = D i - 2xi + 1

goto 1

4 finish

Растрова розгортка суцільних областей

До цих пір мова йшла про подання на растровому графічному пристрої відрізків прямих ліній. Однак одним з унікальних характеристик такого пристрою є можливість подання суцільних областей. Генерацію суцільних областей з простих описів ребер чи вершин називати растрової розгорткою суцільних областей, заповненням багатокутників або заповненням контурів. Для цього можна використовувати кілька методів, які зазвичай діляться на дві широкі категорії: растрова розгортка та затравочное заповнення.

У методах растрової розгорнення намагаються визначити в порядку

сканування рядків, чи лежить точка всередині багатокутника або контуру. Ці алгоритми зазвичай йду від "верху" багатокутника або контуру до "низу".

У методах затравочного заповнення передбачається, що відома деяка точка (запал) всередині замкнутого контуру. В алгоритмах шукають точки, сусідні з затравочной розташовані всередині контуру. Якщо сусідня точка розташована не усередині, значить, виявлена ​​межа контуру. Якщо ж точка опинилася всередині контуру, то вона стає новою затравочной точкою і пошук триває рекурсивно.

Растрова розгортка багатокутників

Можна розробити ефективний метод растрової розгортки багатокутників, якщо скористатися тим фактом, що сусідні пікселі, ймовірно, мають однакові характеристики (крім пікселів граничних ребер). Це властивість називається просторової когерентністю.

2.7 Растрова розгортка суцільний області

Характеристики пікселів на цьому рядку змінюються лише там, де ребро багатокутника перетинає рядок. Ці перетину ділять скануючу рядок на області.

Для простого многокутника на рис. 2.7 рядок 2 перетинає багатокутник при x = 1 і x = 8.

Отримуємо три області:

x <1вне багатокутника

1 £ x £ = "Times New Roman"> 8внутрі багатокутника

x> 8вне багатокутника

Рядок 4 ділиться на п'ять областей:

x <1вне багатокутника

1 £ x £ 4внутрі багатокутника

4 <x <бвне багатокутника

б £ x £ 8внутрі багатокутника

x> 8вне багатокутника

Зовсім необов'язково, щоб точки перетину для рядка 4 відразу визначалися у фіксованому порядку (зліва направо). Наприклад, якщо багатокутник задається списком вершин P1, P2, P3, P4, а список ребер - послідовними парами вершин P1P2, P2P3, P3P4, P4P5, P5P1, то для рядка 4 знайдуть такі точки перетину з ребрами багатокутника: 8, 6, 4 , 1. Ці точки треба відсортувати в порядку зростання x, тобто отримати 1,4, 6, 8.

При визначенні інтенсивності, кольору та відтінку пікселів на скануючої рядку розглядаються пари відсортованих точок перетинань. Для кожного інтервалу, що задається парою перетинань, використовується інтенсивність або колір заповнюваного багатокутника. Для інтервалів між парами перетинань і крайніх (від початку рядка до першої точки перетину і від останньої точки перетину до кінця рядки) використовується фонова інтенсивність або колір.

2.8 Системи координати рядків сканування.

Точне визначення тих пікселів, які повинні активуватися, вимагає деякої обережності. Розглянемо простий прямокутник, зображений на рис. 2.8. Прямокутник має координати (1,1), (5,1), (5,4), (1,4). Скануючі рядки з 1 по 4 мають перетину з ребрами багатокутника при x = 1 і 5. Пиксел адресується координатами свого лівого нижнього кута, значить, для кожної з цих скануючих рядків будуть активовані пікселі з x-координатами 1, 2, 3, 4 і 5. На рис. 2.8 показаний результат. Зауважимо, що площа, що покривається активованими пікселями, дорівнює 20, в той час як справжня площа прямокутника дорівнює 12.

Модифікація системи координат сканує рядки і тесту активації усуває цю проблему, як це показано на рис. 2.8, b. Вважається, що скануючі рядки проходять через центр рядків пікселів, тобто через середину інтервалу, як це показано на рис. 2.8, b. Тест активації модифікується наступним чином: перевіряється, чи лежить всередині інтервалу центр піксела, розташованого праворуч від перетину. Однак пікселі досі адресуються координатами лівого нижнього кута. Як показано на рис.2.8, b, результат цього методу коректний.

Горизонтальні ребра не можуть перетинати скануючу рядок і, таким чином, ігноруються. Це зовсім не означає, що їх немає на малюнку. Ці ребра формуються верхньої і нижньої рядками пікселів.

Додаткова складність виникає при перетині сканує рядки і багатокутника точно по вершині, як це показано на рис. 2.9. При використанні угоди про середину інтервалу між сканирующими рядками одержуємо, що рядок у = 3.5 перетне багатокутник в 2, 2 і 8, т. е. вийде непарна кількість перетинів. Отже, розбивка пікселів на пари дасть невірний результат, тобто пікселі (0,3), (1,3) і від (3,3) до (7,3) будуть фоновими, а пікселі (2,3), (8,3), (9,3) забарвляться в колір багатокутника. Якщо враховувати тільки одну точку перетину з вершиною. Тоді для рядки у = 3.5 одержимо правильний результат. Проте результат застосування методу до рядка у = 1.5, має два перетину в (5,1), показує, що метод невірний. Для цього рядка саме розбивка на пари дасть вірний результат, тобто забарвлений буде лише піксел (5,1). Якщо ж враховувати в вершині лише одне перетинання, то пікселі від (0,1) до (4,1) будуть фоновими, а пікселі від (5,1) до (9,1) будуть пофарбовані в колір багатокутника.

2.9 Особливості перетину з рядками сканування.

Правільнийрезультат можна отримати, враховуючи точку перетину у вершині два різу, якщо вона є точкою локального мінімуму або максимуму і враховуючи раз в іншому випадку. Визначити локальний максимум або мінімум багатокутника в розглянутій вершині можна за допомогою перевірки кінцевих точок двох ребер. Якщо в обох ребер у більше, ніж у вершини, значить, вершина є точкою локального мінімуму. Якщо менше, значить, вершина - точка локального максимуму. Якщо один більше, а інша менше, отже, вершина ні точкою локального мінімуму, ні точкою локального максимуму. На ріс.2.10 точка Р1 - локальний мінімум, Р3 - локальний максимум, а Р2, Р4 - ні те ні інше. Отже, в точках Р1 і Р3 враховуються два перетину з сканирующими

рядками, а Р2 і Р4 - одне.

Алгоритм з впорядкованим списком ребер

Використовуючи описані вище методи, можна розробити ефективні алгоритми растрової розгортки суцільних областей, звані алгоритмами з впорядкованим списком ребер. Ефективність цих алгоритмів залежить від ефективності сортування. Наведемо дуже простий алгоритм.

Алгоритм з впорядкованим списком ребер, що використовує список активних ребер.

Підготувати дані:

Використовуючи скануючі рядки, проведені через середини відрізків, тобто через у + ½ визначити для кожного ребра багатокутника найвищу скануючу рядок, перерізану ребром.

Занести ребро багатокутника в у-групу, відповідну цієї скануючої рядку.

Зберегти в зв'язковому списку значення: початкове значення координат x точок перетину, D y - число скануючих рядків, що пересікаються ребром багатокутника, і ~ D x - крок збільшення по x при переході від однієї скануючої рядку до іншого.

Перетворити ці дані в растрову форму:

Для кожної скануючої рядки перевірити відповідну у-групу на наявність нових ребер. Нові ребра додати до списку активних ребер.

Відсортувати координати x точок перетину з САР в порядку зростання; тобто х1 передує x2, якщо х1 <х2

Виділити пари точок перетинань з відсортованого по

x списку. Активувати на скануючої рядку y пікселі для цілих значень x, таких, що x1 £ x + ½ £ x2. Для кожного ребра з САР зменшити D у на 1. Якщо D у <0, то виключити дане ребро з САР. Обчислити нове значення координат x точок перетину xнов = xстар + D x

Перейти до наступної скануючої рядку

В алгоритмі передбачається, що всі дані попередньо перетворені в уявлення, прийняте для багатокутників.

Алгоритм заповнення по ребрах

Алгоритм, що використовує список ребер і прапор, є двох кроковим. Перший крок полягає в змалюванні контуру, у результаті чого на кожній скануючої рядку утворюються пари обмежують пікселів. Другий крок полягає в заповненні пікселів, розташованих між обмежують. Більш точно алгоритм можна сформулювати в наступному вигляді:

Алгоритм з переліком ребер і прапором

Змалювання контуру:

Використовуючи угоди про середину інтервалу між сканирующими рядками для кожного ребра, перетинає сканирующую рядок, відзначити самий лівий піксел, центр якого лежить праворуч від перетину; тобто

x + 1 / 2> xпересеченія

Заповнення:

Для кожної сканує рядки, що перетинає багатокутник

Усередині = FALSE

for x = 0 (ліва межа) to x = xmax, (права кордон)

if піксел в точці x має граничне значення

then інвертувати значення змінної Всередині

if Усередині = TRUE then

присвоїти пикселу в x значення кольору багатокутника

else

присвоїти пикселу в x значення кольору фону

end if

next x

У даному алгоритмі кожен піксел обробляється тільки один раз, так що витрати на введення / висновок значно менше, ніж в алгоритмі зі списком ребер, в результаті чого, за його апаратної реалізації, він працює на один-два порядки швидше ніж алгоритм з впорядкованим списком ребер .

Алгоритми заповнення з запалом

У обговорювали вище алгоритми заповнення відбувається у порядку сканування. Інший підхід використовується в алгоритмах заповнення з запалом. У них передбачається, що відомий хоча б один піксел з внутрішньої області багатокутника. Алгоритм намагається знайти і зафарбувати всі інші пікселі, належать внутрішньої області. Області можуть бути або внутрішні, або гранично-визначені.

Рис. 2.10. Внутрішньо - певна область

Рис. 2.11. Гранично-певна область

Якщо область належить до внутрішньо - певним, то всі пікселі, належать внутрішньої частини, мають один і той же колір або інтенсивність, а всі пікселі, зовнішні по відношенню до області, мають інший колір. Це продемонстровано на рис. 2.10. Якщо область належить до гранично-визначеним, то всі пікселі на межі області мають виділений значення або колір, як це показано на рис. 2.11. Алгоритми, заповнюють внутрішньо - певні області, називаються внутрішньо - заполняющими, а алгоритми для гранично-визначених областей - гранично-заполняющими. Далі будуть обговорюватися гранично-заповнюють алгоритми, однак відповідні внутрішньо заповнюють алгоритми можна отримати аналогічним чином.

Внутрішньо-або гранично-певні області можуть бути 4 - або 8 - зв'язковими. Якщо область 4-зв'язкова, будь-який піксел в області можна досягти за допомогою комбінацій рухів лише у 4-х напрямах: наліво, направо, вгору, вниз. Для 8-и зв'язковою області додаються ще й діагональні напрями. Алгоритм заповнення 8-зв'язковий області заповнить і 4-зв'язну, але зворотне не вірно. Однак у ситуації, коли потрібно заповнити різними квітами дві окремі 4-зв'язні області, використання 8-зв'язкового алгоритму дасть вірний результат. Далі мова піде про алгоритми для 4-зв'язних областей, проте їх легко адаптувати і для 8-зв'язкових.

Порядковий алгоритм заповнення з запалом

Використовуючи стік, можна розробити алгоритм заповнення гранично-певній галузі. Стік - це масив або інша структура даних, у якому можна послідовно поміщати значення і з якої їх можна послідовно витягувати. Як показує практика, стек може бути досить великим. Найчастіше у ньому міститься дублирующаяся інформація. У построчном алгоритмі заповнення з запалом стік мінімізується за рахунок зберігання лише затравочного піксела для будь-якого безперервного інтервалу на скануючої рядку. Безперервний інтервал - це група прилеглих один до одного пікселів (обмежена вже заповненими чи граничними пікселями). Ми для розробки алгоритму використовуємо евристичний підхід, проте також може бути теоретичний підхід, заснований на теорії графів.

Даний алгоритм застосуємо гранично-визначеним 4-зв'язковим областям, які можуть бути як опуклими, так і не опуклими, а також можуть містити діри. В області, зовнішньої і пов'язаної з нашої, не повинно бути пікселів з кольором, яким область чи багатокутник заповняться. Схематично роботу алгоритму можна розбити на чотири етапи.

Порядковий алгоритм заповнення з запалом

Затравочний піксел на інтервалі вилучають із стека, що містить затравочное пікселі.

Інтервал з затравочних пикселом заповнюється вліво і вправо від початку вздовж скануючої рядки до того часу поки не буде знайдена кордон.

У змінній Xлев і Xправ запам'ятовуються крайній лівий і правий крайній пікселі інтервалу

У діапазоні Xлев £ x £ Xправ перевіряються рядки розташовані безпосередньо над в під поточним рядком. Визначається, чи є на них ще не заповнені пікселі. Якщо такі пікселі є (тобто не всі пікселі граничні, або вже заповнені), то в зазначеному діапазоні крайній правий піксел в кожному інтервалі відзначається як затравочний і міститься в стек.

При ініціалізації алгоритму в стек збожеволіє єдиний затравочний пікселів, робота завершується при спустошенні стека. Нижче наводиться більш докладний опис алгоритму на псевдокоде.

Порядковий алгоритм заповнення з запалом

Запал (x, y) видає затравочний піксел

Pop-процедура, яка витягує піксел з стека

Push - процедура, яка поміщає піксел в стек

ініціюємо стек

Push Запал (x, y)

While (стек не порожній)

Витягаємо піксел з стека і присвоюємо йому нове значення Pop Піксель (x, y)

Піксель (x, y) = Нов_значеніе

зберігаємо x-координату затравочного піксела

Врем_х = x

заповнюємо інтервал праворуч від затравки

x = x +1

while Піксель (x, y) ¹ Гран_значеніе

Піксель (x, y) = Нов_значеніе

x = x +1

end while

зберігаємо крайній праворуч піксел

Xправ = x - 1

відновлюємо x-координату початку

x = Врем_х

заповнюємо інтервал зліва початку

x = x - 1

while Піксель (x, y) ¹ Гран_значеніе

Піксель (x, y) = Нов_значеніе

x = x - 1

end while

зберігаємо крайній зліва піксел

Xлев = x +1

відновлюємо x-координату початку

x = Врем_х

перевіримо, що рядок вище не є ні кордоном багатокутника, ні вже повністю заповненої; якщо це не так, то знайти приманку, починаючи з лівого краю подинтервала сканує рядки

x = Xлев

y = y +1

while x £ Xправ

шукаємо приманку на рядку вище

Прапор = 0

while (Піксель (x, y) ¹ Гран_значеніе and

Піксель (x, y) ¹ Нов_значеніе and x <Xправ)

if Прапор = 0 then Прапор = 1

x = x + 1

end while

поміщаємо в стек крайній праворуч піксел

if Прапор = 1 then

if (x = Xправ and Піксель (x, y) ¹ Гран_значеніе and Піксель (x, y) ¹ Нов_значеніе) then

Push Піксель (x, y)

else

Push Піксель (x - 1, y)

end if

Прапор = 0

end if

продовжимо перевірку, якщо інтервал був перерваний

Xвход = x

while ((Піксель (x, y) = Гран_значеніе or

Піксель (x, y) = Нов_значеніе) and x <Xправ)

x = x + 1

end while

впевнитись що координата піксела збільшена

if x = Xвход then x = x + 1

end while

перевіримо, що рядок нижче не є ні кордоном багатокутника, ні вже повністю заповненої

Ця частина алгоритму абсолютно аналогічна перевірці для рядки вище, за винятком, того що замість y = y + 1 треба підставити y = y - 1

end while

finish

Видалення невидимих ​​ліній і поверхонь

Завдання видалення невидимих ​​ліній і поверхонь є однією з найбільш складних у машинній графіці. Алгоритми видалення невидимих ​​ліній і поверхонь служать для визначення ліній ребер, поверхонь чи обсягів, які видимі чи невидимі для спостерігача, що знаходиться в заданій точці простору.

3.1 Необхідність видалення невидимих ​​ліній

Необхідність видалення невидимих ​​ліній, ребер, поверхонь чи обсягів проілюстрована рис.3.1. На рис.3.1, а наведено типовий каркасний креслення куба. Його можна інтерпретувати двояко: як вид куба зверху, зліва чи знизу, праворуч. Видалення тих ліній або поверхонь, які невидимі з відповідної точки зору, дають змогу уникнути неоднозначності. Результати показані на рис.3.1, b і c.

Складність завдання видалення невидимих ​​ліній і поверхонь призвела до появи великої частини, різних способів її рішення. Багато хто з них орієнтовані на спеціалізовані програми. Найкращого рішення загальної задачі видалення невидимих ​​ліній і поверхонь не існує. Для моделювання процесів в реальному часі, наприклад, для авіа тренажерів, потрібні швидкі алгоритми, які можуть породжувати результати з частотою відео генерації (30 кадр / с). Для машинної мультиплікації потрібні алгоритми, які можуть генерувати складні реалістичні зображення, в яких представлені тіні, прозорість і фактура, що враховують ефекти віддзеркалення і заломлення кольору в дрібних відтінках. Подібні алгоритми працюють повільно, і часто на обчислення потрібно кілька хвилин або навіть годин. Строго кажучи, облік ефектів прозорості, фактури, відблиски і т. п. не входить у завдання видалення невидимих ​​ліній або поверхонь. Природніше вважати їх частиною процесу візуалізації зображення. Процес візуалізації є інтерпретацією або поданням зображення чи сцени в реалістичній манері. Однак багато хто з цих ефектів вмонтовані в алгоритми видалення невидимих ​​поверхонь і тому будуть зачеплені. Існує тісний взаємозв'язок між швидкістю роботи алгоритму і детальністю його результату. Жоден з алгоритмів не може досягти хороших оцінок для цих двох показників одночасно. У міру створення все більш швидких алгоритмів можна будувати все більш детальні зображення. Реальні завдання, однак, завжди будуть вимагати врахування ще більшої кількості деталей.

Алгоритми видалення невидимих ​​ліній або поверхонь можна класифікувати за способом вибору системи координат або простору, в якому вони працюють. Алгоритми, що працюють в об'єктному просторі, мають справу з фізичною системою координат, у якій описані ці об'єкти. При цьому виходять дуже точні результати, обмежені, власне кажучи, лише точністю обчислень. Отримані зображення можна вільно збільшувати в багато разів. Алгоритми, що працюють в об'єктному просторі, особливо корисні в тих додатках, де необхідна висока точність. Алгоритми ж, що працюють в просторі зображення, мають справу з системою координат того екрана, на якому об'єкти візуалізуються. При цьому точність обчислень обмежена роздільну здатність екрану. Результати, отримані в просторі зображення, а потім збільшені в багато разів, не будуть відповідати початковій сцені. Алгоритми, формують список пріоритетів працюють поперемінно в обох згаданих системах координат.

Обсяг обчислень для будь-якого алгоритму, що працює в об'єктному просторі, і порівняв кожен об'єкт сцени із іншими об'єктами цієї сцени, зростає теоретично як квадрат числа об'єктів (n2). Аналогічно, обсяг обчислень будь-якого алгоритму, що працює в просторі зображення і порівняв кожен об'єкт сцени з позиціями всіх пікселів у системі координат екрана, зростає теоретично, як nN. Тут n позначає кількість об'єктів (тел, площин чи ребер) в сцені, а N - кількість пікселів. Теоретично трудомісткість алгоритмів, работаюoих в об'єктному просторі, менше трудомісткості алгоритмів, що працюють в просторі зображення, при n <N. Оскільки N звичайно дорівнює (512) 2, то теоретично більшість алгоритмів слід реалізовувати в об'єктному просторі. Однак на практиці це не так. Справа в тому, що алгоритми, що працюють в просторі зображення, ефективні тому, що для них легше скористатися перевагою когерентності при растрової реалізації.

Далі дається виклад деяких алгоритмів, що працюють як в об'єктному просторі, так і в просторі зображення. Кожен з них ілюструє одну чи кілька основних ідей теорії алгоритмів видалення невидимих ​​ліній і поверхонь.

Алгоритм плаваючого горизонту

Алгоритм плаваючого горизонту найчастіше використовується для видалення невидимих ​​ліній тривимірного представлення функцій, що описують поверхню у вигляді

F (x, у, z) = 0

Подібні функції виникають у багатьох додатках у математиці, техніці, природних науках та інших дисциплінах.

Існує багато алгоритмів, що використовують цей підхід. Бо у додатках основному нас цікавить опис поверхні, цей алгоритм зазвичай працює в просторі зображення. Головна ідея цього методу полягає в зведенні тривимірної задачі до двовимірної шляхом перетину вихідної поверхні послідовністю паралельних січних площин, що мають постійні значення координат x, y або z.

Січні площини з постійною координатою

На рис. 3.2 наведено приклад, де зазначені паралельні площині визначаються постійними значеннями z. Функція F (x, у, z) = 0 зводиться до послідовності кривих, що у кожної з цих паралельних площин, наприклад до послідовності

y = f (x, z) або y = g (y, z)

де z постійно на кожній із заданих паралельних площин.

Отже, поверхня тепер складається з послідовності кривих, що у кожної з цих площин, як показано на рис. 3.3. Тут передбачається, що отримані криві є однозначними функціями незалежних змінних. Якщо спроектувати отримані криві на площину z = 0, то одразу стає зрозуміла ідея алгоритму видалення невидимих ​​ділянок вихідної поверхні. Алгоритм спочатку впорядковує площині z = const зі збільшення відстані до них від точки спостереження. Потім для кожної площині, починаючи з найближчого до точки спостереження, будується крива, що у ньому. Алгоритм видалення невидимої лінії полягає в наступному:

Якщо на поточному площині при деякому заданому значенні x відповідне значення y на кривій більше значення y для всіх попередніх кривих при цьому значенні x, то поточна крива видимою у цій точці, в іншому випадку вона невидима.

Реалізація даного алгоритму є досить простою.

3.4 Обробка нижньої сторони поверхні

Для зберігання максимальних значень y при кожному значенні x використовується масив, довжина якого дорівнює числу помітних точок (дозволу) по осі x в просторі зображення. Значення, які у цьому масиві, є поточні значення "горизонту". Тому в міру малювання кожної чергової кривою цей горизонт "спливає". Фактично цей алгоритм видалення невидимих ​​ліній працює кожен раз з однією лінією.

Алгоритм працює дуже добре до тих пір, поки яка-небудь чергова крива не виявиться нижче найпершою з кривих. Як показано на рис.3.4, а. Такі криві, природно, видимі і є нижню сторону вихідної поверхні. Однак алгоритм буде вважати їх невидимими. Нижня сторона поверхні робиться видимої, якщо модифікувати цей алгоритм, включивши до нього нижній горизонт, який опускається вниз по ходу роботи алгоритму. Це реалізується за допомогою другого масиву, довжина якого дорівнює числу помітних точок по осі x в просторі зображення. Цей масив містить найменші значення y для кожного значення x. Алгоритм тепер стає таким:

Якщо на поточному площині при деякому заданому значенні x відповідне значення y на кривій більше максимуму менше мінімуму по y для всіх попередніх кривих при цьому x, то поточна крива видима. В іншому випадку вона невидима.

Отриманий результат показаний на рис. 3.4, b.

У викладеному алгоритмі передбачається, що значення функції, тобто y, відомо для кожного значення x в просторі зображення. Однак якщо для кожного значення x не можна вказати (обчислити) відповідне йому значення у, то неможливо підтримувати масиви верхнього та нижнього плаваючих горизонтів. У такому випадку використовується лінійна інтерполяція значень у між відомими значеннями для того, щоб заповнити масиви верхнього та нижнього плаваючих горизонтів, як показано на рис. 3.5.

3.5 Лінійна інтерполяція між заданими точками

3.6. Ефект від перетинання кривих

Якщо видимість кривої змінюється, то метод з такою простою інтерполяцією дасть коректного результату. Цей ефект проілюстровано рис. 3.6, а. Припускаючи, що операція по заповненню масивів проводиться після перевірки видимості, отримуємо, що при переході поточної кривої від видимого до невидимого станом (сегмент АВ на рис. 3.6, а), крапка (xn + k, yn + k) оголошується невидимою. Тоді ділянка кривої між точками (xn, yn) і (xn + k, yn + k) не зображується і операція щодо заповнення масивів не проводиться. Утворюється зазор між поточної і попередньої кривими Якщо ділянці поточної кривою відбувається перехід від невидимого стану до видимого (сегмент CD на рис. 3.6, а), то точка (xm + k, ym + k) оголошується видимої, а ділянка кривої між точками ( xm, ym) і (xm + k, ym + k) зображується і операція щодо заповнення масивів проводиться. Тому змальовується і невидимий шматок сегмента CD. Крім того, масиви плаваючих горизонтів не будуть містити точних значень у. А це може спричинити за собою додаткові небажані ефекти для наступних криві. Отже,

необхідно вирішувати задачу про пошук точок перетину сегментів поточної і попередньої кривих.

Існує кілька методів отримання точок перетину кривих. На растрових дисплеях значення координати x можна збільшувати на 1, починаючи з xn або xm (рис. 3.6, а). Значення у, відповідне поточному значенням координати х у просторі зображення, виходить шляхом додавання до значення у, відповідному попередньому значенням координати x, вертикального збільшення D y уздовж заданої кривої. Потім визначається видимість нової точки з координатами (x + 1, y + D y). Якщо ця точка видимою, то активується пов'язаний з нею піксел. Якщо невидима, то піксел не активується, а x збільшується на 1. Цей процес продовжується до тих пір, поки не зустрінеться xn + k або xm + k. Перетин для растрових дисплеїв визначаються викладеним методом з достатньою точністю. Близький і навіть більш елегантний метод визначення перетинань грунтується на двійковому пошуку.

Точне значення точки перетину двох прямолінійних відрізків, які интерполируют поточну і попередню криві, між точками (xn, yn) і (xn + k, yn + k) (рис. 3.6) задається формулами:

де

а індекси c і p відповідають поточної і попередньої кривим. Отриманий результат показаний на рис. 3.6, b. Тепер алгоритм викладається більш формально.

Якщо на поточному площині при деякому заданому значенні x відповідне значення y на кривій більше максимуму менше мінімуму по y для всіх попередніх кривих при цьому x, то поточна крива видима. В іншому випадку вона невидима.

Якщо на ділянці від попереднього (xn) до поточного (xn + k) значення x видимість кривої змінюється, то обчислюється точка перетину (xi).

Якщо на ділянці від xn до xn + k сегмент кривої повністю бачимо, то він зображується цілком; якщо він став невидимим, то змальовується фрагмент від xn до xi, якщо ж він став видимим, то змальовується фрагмент від xi до xn + k.

Заповнити масиви верхнього та нижнього плаваючих горизонтів.

Викладений алгоритм, що призводить до деяких дефектів, коли крива, що в одній з більш віддалених від точки спостереження площин, з'являється зліва чи справа з-під безлічі кривих, що у площинах, які ближче до зазначеної точці спостереження. Цей ефект продемонстровано на рис. 3.7, де вже оброблені площині n - 1 і n розташовані ближче до точки спостереження. На малюнку показано, що при обробці площині n + 1. Після обробки кривих n - 1 і n верхній горизонт для значень x = 0 і 1 дорівнює початковому значенням у; для значень x від 2 до 17 він дорівнює ординатам кривої n; а для значень 18, 19, 20 - ординатам кривої n - 1. Нижній горизонт для значень x = 0 і 1 дорівнює початковому значенням у; для значень x = 2, 3, 4 - ординатам кривої n; а значень x від 5 до 20 - ординатам кривої n - 1. При обробці поточної кривою (n + 1) алгоритм оголошує її видимої при x = 4. Це показано суцільною лінією на рис. 3.7.

3.7 Ефект зазубреного ребра

Аналогічний ефект і його справа при x = 18. Такий ефект призводить до появи зазубрених бічних ребер. Проблема з зазубренностью бічних ребер вирішується включенням в масиви верхнього та нижнього горизонтів ординат, відповідних штриховим лініях на рис. 3.7. Це можна виконати ефективно, створивши хибні бічні ребра. Наведемо алгоритм, який реалізує цю ідею для обох ребер.

Обробка лівого бічного ребра:

Якщо Pn є першою точкою на першій кривої, то запам'ятаємо Pn як Pn-1 і закінчимо заповнення. В іншому випадку створимо ребро, що з'єднує Pn і Pn-1.

Занесемо в масиви верхнього та нижнього горизонтів ординати цього ребра і запам'ятаємо Pn як Pn-1.

Обробка правого бокового ребра:

Якщо Pn є останньою крапкою на першій кривої, то запам'ятаємо Pn як Pn-1 і закінчимо заповнення. В іншому випадку створимо ребро, що з'єднує Pn і Pn-1.

Занесемо в масиви верхнього та нижнього горизонтів ординати цього ребра і запам'ятаємо Pn як Pn-1.

Тепер повний алгоритм виглядає так:

Для кожної площині z = const.

Обробити ліве бокове ребро.

Для кожної точки, що лежить на кривій з поточної площині:

Якщо при деякому заданому значенні x відповідне значення у на кривою більше максимуму менше мінімуму по у всіх попередніх кривих при цьому x, то крива видимою (у цій точці). В іншому випадку вона невидима.

Якщо на сегменті від попереднього (xn) до поточного (xn + k) значення x видимість кривої змінюється, то обчислюється перетин (xi).

Якщо на ділянці від xn до (xn + k) сегмент кривої повністю бачимо, то він зображується цілком; якщо він cтал невидимим, то змальовується його шматок від xn до xi, якщо ж він став видимим, то змальовується його шматок від xi до xn + k.

Заповнити масиви верхнього та нижнього плаваючих горизонтів.

Обробити праве бокове ребро.

Якщо функція містить дуже гострі ділянки (піки), то наведений алгоритм може дати некоректні результати. Для уникнення цього якщо зустрічаються вузькі ділянки, то функцію слід обчислювати в більшій кількості точок.

3.8 Функція y = (1 / 5) sin x cos z - (3 / 2) cos (7a / 4) * exp (- a), a = (x - p) 2 + (z - p) 2, зображена в інтервалі (0, 2p) за допомогою алгоритму плаваючого горизонту

На рис. 3.8 показаний типовий результат роботи алгоритму плаваючого горизонту. Запис цього алгоритму наводитися нижче.

Алгоритм плаваючого горизонту

Гекран - дозвіл екрану в горизонтальному напрямку

Векран - дозвіл екрану в вертикальному напрямку

Верх - масив, що містить координати верхнього горизонту

Низ - масив, що містить координати нижнього горизонту

Y - поточне значення функції y = f (x, z) при z = const

Тфлаг - прапор видимості для поточної точки

Пфлаг - прапор видимості для попередньої точки, рівний

0 = невидима

1 = видимою і від верхнього горизонту

-1 = Видимою і від нижнього горизонту

Draw - графічна команда, яка креслить видиму лінію між точками, заданими їх координатами.

Xmin, Xmax - мінімальна та максимальна абсциси функції

Xшаг - крок збільшення вздовж осі x

Zmin, Zmax - мінімальна та максимальна аппликата функції

Zшаг - крок між площинами z = const

Dimension Верх (Гекран), Дно (Гекран)

ініціалізація змінних

Xлев = - 1; Yлевое = - 1; Xправ = - 1; Yправое = - 1

ініціалізація масивів горизонтів

Верх = 0

Низ = Векран

Обчислення функції на кожній площині z = const, починаючи з найближчої до спостерігача площині Zmax

for z = Zmax to Zmin step - Zшаг

ініціалізація попередніх значень за x і y: Xпред і Yпред

Xпред = Xmin

Yпред = f (Xmin, z)

якщо використовується видове перетворення, її потрібно застосувати до Xпред, Yпред, z в даній точці

обробка лівого бічного ребра

call Обрребра (Xпред, Yпред, Xлев, Yлев; Верх, Низ)

call Видимість (Xпред, Yпред, Верх, Низ; Пфлаг)

для кожної точки на кривій, що лежить в площині z = const

for x = Xmin to Xmax step Xшаг

y = f (x, z)

якщо використовується видове перетворення, її потрібно застосувати до даного пункту

перевірка видимості поточної крапки й заповнення відповідного масиву горизонту

call Видимість (x, y, Верх, Низ; Тфлаг)

if Тфлаг = Пфлаг then

if (Тфлаг = 1) or (Тфлаг = - 1) then

Draw (Xпред, Yпред, x, y)

call Горизонт (Xпред, Yпред, x, y; Верх, Низ)

end if

якщо видимість змінилася, то обчислюється те і заповнюється масив горизонту

else

if Тфлаг = 0 then

if Пфлаг = 1 then

call Перетин (Xпред, Yпред, x, y, Верх; Xi, Yi)

else

call Перетин (Xпред, Yпред, x, y, Низ; Xi, Yi)

end if

Draw (Xпред, Yпред, Xi, Yi)

сall Горизонт (Xпред, Yпред, Xi, Yi, Верх, Низ)

else

if Тфлаг = 1 then

if Пфлаг = 0 then

call Перетин (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y)

сall Горизонт (Xi, Yi, x, y; Верх, Низ)

else

call Перетин (Xпред, Yпред, x, y, Низ; Xi, Yi)

Draw (Xпред, Yпред, Xi, Yi)

call Горизонт (Xпред, Yпред, Xi, Yi; Верх, Низ)

call Перетин (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y)

call Горизонт (Xi, Yi, x, y; Верх, Низ)

end if

else

if Пфлаг = 0 then

call Перетин (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y)

call Горизонт (Xi, Yi, x, y; Верх, Низ)

else

call Перетин (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xпред, Yпред, Xi, Yi)

call Горизонт (Xпред, Yпред, Xi, Yi; Верх, Низ)

call Перетин (Xпред, Yпред, x, y, Низ; Xi, Yi)

Draw (Xi, Yi, x, y)

call Горизонт (Xi, Yi, x, y; Верх, Низ)

end if

end if

end if

end if

знову ініціалізувати Пфлаг, Xпред, Yпред

Пфлаг = Тфлаг

Xпред = x

Yпред = y

next x

обробка правого кінцевого ребра

call Обрребра (x, y, Xправ, Yправ; Верх, Низ)

next z

finish

підпрограма обробки бічного ребра

Subroutine Обрребра (x, y, Xребра, Yребра; Верх, Низ)

якщо Xребра = - 1, то зустрінута перша крива і ребро не створюється

if Xребра = - 1 then 1

call Горизонт (Xребра, Yребра, x, y; Верх, Низ)

1 Xребра = x

Yребра = y

return

підпрограма визначення видимості точки

Subroutine Видимість (x, y, Верх, Низ; Тфлаг)

видимість точки визначається по відношенню до верхнього і нижнього плаваючим обріїв. Якщо точка лежить на самому обрії, то вона вважається видимою.

Тфлаг = 0, якщо точка невидима

= 1, якщо вона видимою і вище верхнього горизонту

= - 1, якщо вона видимою і від нижнього горизонту

x вважається цілої

if (y <Верх (x)) and (y> Низ (x)) then Тфлаг = 0

if y ³ Верх (x) then Тфлаг = 1

if y £ Низ (x) then Тфлаг = - 1

return

підпрограма заповнення масивів плаваючих горизонтів

Subroutine Горизонт (X1, Y1, X2, Y2; Верх, Низ)

Ця програма використовує лінійну інтерполяцію заповнення масивів горизонтів між X1 і X2

Max (a, b) - визначає більше з a і b

Min (a, b) - визначає менше з a і b

перевірка вертикальності нахилу

if (X2 - X1) = 0 then

Верх (X2) = Max (Верх (X2), Y2)

Низ (X2) = Min (Низ (X2), Y2)

else

Нахил = (Y2 - Y1) / (X2 - X1)

for x = X1 to X2 step 1

y = Нахил * (x - X1) + Y1

Верх (x) = Max (Верх (x), y)

Низ (x) = Min (Низ (x), y)

next x

end if

return

підпрограма обчислення перетину поточної кривою з горизонтом

Subroutine Перетин (X1, Y1, X2, Y2, Масив; Xi, Yi)

Ця процедура обчислює перетин двох відрізків прямих

Масив містить інформацію про відповідний горизонті

Sign - функція приймає значення - 1, 0, 1, якщо знак її аргументу 0 відповідно

перевірка нескінченності нахилу

if (X2 - X1) = 0 then

Xi = X2

Yi = Масив (X2)

else

обчислення перетину

обхід починається з самої лівої використовуваної точки

перетин вважається виявленим, коли змінюється знак різниці значень y

Нахил = (Y2 - Y1) / (X2 - X1)

Ysign = Sign (Y1 + Нахил - Масив (X1 + 1))

Csign = Ysign

Yi = Y1 + Нахил

Xi = X1 + 1

while Csign = Ysign

Yi = Y1 + Нахил

Xi = X1 + 1

Csign = Sign (Yi - Масив (Xi))

end while

вибирається найближче ціле число

if | Yi - Нахил - Масив (X1 - 1) | £ | Yi - Нахил - Масив (X1) | then

Yi = Y1 - Нахил

Xi = X1 - 1

end if

end if

return

У наведених вище алгоритмі і прикладі функція у = f (x, z) розглядалася тільки при z = const. Часто буває зручно викреслювати криві, вважаючи постійними як z, так і x. При цьому виникає ефект перехресної штрихування. На перший погляд може здатися, що перехресну штрихування можна отримати шляхом накладення двох результатів, утворених площинами z = const і x = const. Однак це не так. Вірний результат виходить при обробці тих кривих у складі що у площинах z = const і x = const, які ближче всього до горизонтальних при звичайному порядку їх слідування. Однак після обробки кожної кривою, близькою до горизонтальної, необхідно обробляти ділянки кривих, що лежать в ортогональних їй площинах, які є між зазначеної кривої та кривої, наступного за нею. Зрозуміло, при обробці обох послідовностей кривих потрібно використовувати одні й ті ж масиви верхнього та нижнього плаваючих горизонтів. Якщо використовується перехресна штрихування, то не треба формувати ліве і праве бічні ребра.

Алгоритм Робертса

Алгоритм Робертса є перше відоме рішення задачі про видалення невидимих ​​ліній. Це математично елегантний метод, який працює в об'єктному просторі. Алгоритм, перш за все, видаляє з кожного тіла ті ребра чи грані, які екрануються самим тілом. Потім кожна з видимих ​​ребер кожного тіла порівнюється з кожним із решти тіл визначення того, яка його частина або частини, якщо такі є, екрануються цими тілами. Тому обчислювальна трудомісткість алгоритму Робертса зростає теоретично як квадрат числа об'єктів. Саме цей факт призвів до зниження інтересу до алгоритму Робертса. Проте математичні методи, використовувані в цьому алгоритмі, прості, потужні і точні. Крім того, цей алгоритм можна використовувати для ілюстрації деяких важливих концепцій. Нарешті, більш пізні реалізації алгоритму, використовують попередню пріоритетну сортування вздовж осі z і прості габаритні або мінімаксні тести, демонструють майже лінійну залежність від кількості об'єктів.

В алгоритмі Робертса потрібно, щоб усі зображувані тіла чи об'єкти були опуклими. Неопуклі тіла повинні бути розбиті на випуклі частини. У цьому алгоритмі опукле багатогранне тіло з плоскими гранями має представлятися набором пересічних площин. Рівняння довільній площини в тривимірному просторі має вигляд

ах + by + cz + D = 0 (3.1)

У матричній формі це виглядає так:

або

де представляє собою площину. Тому будь-яка опукле тверде тіло можна сформулювати матрицею тіла, що з коефіцієнтів рівнянь площин, тобто

де кожен стовпець містить коефіцієнти одній площині.

Нагадаємо, що будь-яка точка простору бути подана в однорідних координатах вектором

Більш того, якщо точка [S] лежить на площині, то [S] * [P] T = 0. Якщо ж [S] не лежить на площині, то знак цього скалярного твори показує, по який бік від площини розташована крапка. В алгоритмі Робертса передбачається, що точки, що лежать всередині тіла, дають позитивне скалярний твір.

Хоча рівняння площини (3.1) містить чотири невідомих коефіцієнта, його можна нормувати те, щоб d = 1 отже, трьох неколінеарних точок достатньо для визначення цих коефіцієнтів. Підстановка координат трьох неколінеарних точок (x1, y1, z1), (x2, y2, z2), (x2, y2, z2) на нормований рівняння (3.1) дає:

ax1 + by1 + cz1 = - 1

ax2 + by2 + cz2 = - 1

ax3 + by3 + cz3 = - 1

У матричній формі це виглядає так:

або

(3.2)

Рішення цього рівняння дає значення коефіцієнтів рівняння площини:

Інший спосіб використовується, якщо відомий вектор нормалі до площини, тобто

n = a i + b j + c k

де i, j, k - одиничні вектори осей x, y, z відповідно. Тоді рівняння площини набуде вигляду

ax + by + cz + d = 0 (3.3)

Величина d обчислюється за допомогою довільної точки на площині. Зокрема, якщо компоненти цієї точки на площині (х1, y1, z1) то:

d = - (aх1 + by1 + cz1) (3.4)

Оскільки обсяг обчислень в алгоритми видалення невидимих ​​ліній або поверхонь зростає із збільшенням числа багатокутників, для опису поверхонь вигідно використовувати багатокутники з більш ніж трьома сторонами. Ці багатокутники можуть бути як неопуклих, так і неплоских. Метод, запропонований Мартіном Ньюела, дозволяє знайти як точне рішення для рівнянь площин, містять плоскі многокутники, так і "найкращий" наближення для неплоских багатокутників. Цей метод еквівалентний визначенню нормалі в кожній вершині багатокутника у вигляді векторного добутку прилягають ребер і усереднення результатів. Якщо a, b, c, d - коефіцієнти рівняння площини, то

(3.5)

де

if i = n then j = 1 else j = i + 1

а d обчислюється за допомогою будь-якої точки на площині.

Перед початком роботи алгоритму видалення невидимих ​​ліній або поверхонь для отримання бажаного виду сцени часто застосовується тривимірне видове перетворення. Матриці тіл для об'єктів реформованій сцени можна отримати або перетворенням вихідних матриць тіл або обчисленням нових матриць тіл, використовуючи перетворені вершини або точки.

Якщо [В] - матриця однорідних координат, що становить вихідні вершини тіла, а [Т] - матриця розміром 4х4 видового перетворення, то перетворені вершини такі:

[ВТ] = [В] [T] (3.6)

де [ВТ] - перетворена матриця вершин. Використання рівняння (3.2) дозволяє отримати рівняння вихідних площин, що обмежують тіло:

[В] [V] = [D] (3.7)

де [V] - матриця тіла, а [D] у правій частині - нульова матриця. Аналогічно рівняння перетворених площин задаються наступним чином:

[ВТ] [VТ] = [D] (3.8)

де [VТ] - перетворена матриця тіла. Прирівнюючи ліві частини рівняння (3.7) і (3.8), отримуємо

[ВТ] [VT] = [В] [V]

Підставляючи рівняння (3.6), скорочуючи на [В] і примножуючи зліва на

[T] -1 маємо

[VT] = [T] -1 [V]

Отже, перетворена матриця тіла виходить множенням вихідної матриці тіла зліва на обернену матрицю видового перетворення.

3.8 Не лицьові площині

Той факт, що площині мають нескінченну довжину й що скалярний твір крапки на матрицю тіла негативно, якщо точка лежить поза цим тіла, дозволяє запропонувати метод, в якому матриця тіла використовується для визначення меж, які екрануються самим цим тілом. Негативне скалярний твір дає тільки така площину (стовпець) в матриці тіла, щодо якої точка лежить зовні.

Якщо глядач перебуває в нескінченності на позитивній півосі z і дивиться на початок координат, то його погляд спрямований у бік негативною півосі z. В однорідних координатах вектор такого напрямку дорівнює:

який служить, крім того, спосіб крапки, що у нескінченності на негативній півосі z. Фактично [Є] представляє будь-яку точку, що лежить на площині z = - ¥, тобто будь-яку точку типу (x, y, - ¥). Тому, якщо скалярний твір [Є] на стовпець, відповідний який-небудь площини у матриці тіла, негативно, то [Є] лежить по негативну сторону цій площині. Отже, ці площини невидимі з точки спостереження, що лежить у площині z = ¥, а пробна точка на z = - ¥ екранується самим тілом, як показано на рис. 3.8. Такі площині називаються не лицьовими, а відповідні їм межі задніми. Отже,

[Є] [V] <0

є умовою того, що площині - не лицьові, які межі - задні. Зауважимо, що для аксонометричних проекцій (точка спостереження нескінченності) це еквівалентно пошуку позитивних значень у третьому рядку матриці тіла.

Цей метод є найпростішим алгоритмом видалення невидимих ​​поверхонь для тіл, що становлять одиночні опуклі багатогранники. Цей спосіб часто називають відкиданням задніх площин. Для опуклих багатогранників число граней при цьому скорочується приблизно наполовину. Метод еквівалентний вирахування нормалі до поверхні для кожного окремого багатокутника. Заперечність нормалі до показує, що нормаль направлена ​​у бік від спостерігача і, Отже, даний багатокутник не видно.

Цей метод можна використовувати також і для простої зафарбовування. Інтенсивність або колірної відтінок багатокутника робиться пропорційним проекції нормалі до поверхні на напрям погляду.

Даний метод визначення не лицьових граней в результаті формує аксонометричну проекцію на якусь площину, розташовану нескінченно далеко від будь-якої точки тривимірного простору. Видові перетворення, включаючи перспективне, проводяться до визначення не лицьових площин. Коли видове перетворення включає в себе перспективу, то потрібно використовувати повне перспективне перетворення одного тривимірного простору в інший, а не перспективне проектування певну двовимірну площину. Повне перспективне перетворення призводить до спотворення тривимірного тіла, яке потім проектується на якусь площину в нескінченності, коли лицьові площині вже визначені. Цей результат еквівалентний перспективному проецированию з деякого центру на кінцеву площину проекції.

Видове перетворення можна застосувати до тіла так, щоб точка спостереження залишалася фіксованою. При іншому способі тіло залишається нерухомим. Відповідні точка спостереження і напрямок погляду виходять множенням справа на матрицю, зворотну матриці видового перетворення.

Після визначення нелицьових площин залишається знайти нелицьові відрізки. Нелицевой відрізок утворюється в результаті перетину пари нелицьових площин. Після першого етапу видалення нелицьових відрізків необхідно з'ясувати, чи існують такі відрізки, які екрануються іншими тілами на картинці чи сцені. Для цього кожен залишився відрізок або ребро потрібно порівняти з іншими тілами сцени або картинки. При цьому використання пріоритетною сортування (z-сортування) і простого мінімаксного або габаритного з прямокутною осяжний оболонкою тестів дозволяє видалити цілі групи або кластери відрізків і тіл. Наприклад, якщо всі тіла в сцені упорядковані у певній пріоритетному списку, що використовує значення z найближчих вершин для подання відстані до спостерігача, то ніяке тіло з цього списку, у якого найближча вершина знаходиться далі від спостерігача, ніж сама вилучена з кінцевих точок ребра, не може закривати це ребро. Більше того, жоден з решти тіл, прямокутна оболонка якого розташована повністю справа, зліва, над або під ребром, не може екранувати це ребро. Використання цих прийомів значно скорочує кількість тіл, з якими потрібно порівнювати кожен відрізок або ребро.

Для порівняння відрізка P1P2 з тілом зручно використовувати параметричне представлення цього відрізка:

Р (t) = P1 + (Р2 - P1) t 0 £ t £ 1

v = s + d t

де v - вектор точки на відрізку, s - початкова точка, d - напрям відрізка. Необхідно визначити, чи буде відрізок невидимим. Якщо він невидимий, треба знайти значення t, для яких він невидимий. Для цього формується інший параметричний відрізок від точки Р (t) до точки спостереження g:

Q (a, t) = u = v + g a = s + d t + g a 0 £ t £ 1, a ³ 0

Тут a і t виконують аналогічні функції. Заданий значення t вказує крапку на відрізку P (t), а a вказує крапку на відрізку, проведеному від точки P (t) до точки спостереження. Фактично Q (a, t) являє собою площину в тривимірному просторі. Пара (a, t) визначає точку на цій площині. Значення a позитивно, оскільки тіла, що екранують P (t) можуть бути лише у тієї частини цій площині, яка укладена між відрізком P (t) і точкою спостереження.

Скалярний твір будь-якої точки, що лежить всередині тіла, на матрицю тіла позитивно. Якщо ж точка лежить усередині тіла, то вона невидима. Тому для визначення частини відрізка, яка екранується тілом, досить знайти значення a і t, для яких скалярний твір Q (a, t) = u на матрицю тіла позитивно.

3.9 Схема рішення про a і t

Це скалярний добуток дорівнює:

h = u * [VT] = s * [VT] + t d * [VT] + a g * [VT]> 0 0 £ t £ 1, a ³ 0

Якщо всі компоненти h ненегативні для деяких t і a, відрізок при цих значеннях t екранується даним тілом. Позначимо

p = s * [VT]

q = d * [VT]

w = g * [VT]

запишемо умови у вигляді

hj = pj + tqj + awj 0 £ t £ 1, a ³ 0

де j - номер стовпця в матриці тіла. Ці умови повинні виконуватися при всіх значеннях j, тобто для всіх площин, що обмежують об'єм тіла. Прикордонний випадок між видимістю і невидимість виникає, коли hj = 0. При hj = 0 точка лежить на площині. Вважаючи hj = 0 для всіх площин, ми отримаємо систему рівнянь відносно a і t, які повинні задовольнятися одночасно. Результат можна отримати шляхом спільного розв'язання різноманітних пар рівнянь із цієї системи, при цьому будуть знайдені всі значення a і t, при яких змінюється значення видимості відрізка. Схема рішення показана на рис. 3.10. Число можливих рішень при j рівняннях (площинах) дорівнює j (j - 1) / 2. Кожне рішення, у діапазонах 0 £ t £ 1, a ³ 0, підставляється в інші рівняння для перевірки того, що умова hj ³ 0 виконано. Пошук коректних рішень проводиться для того, щоб знайти мінімальне серед максимальних значень параметра t (tminmax) і максимальне серед мінімальних значень t (tmaxmin). Відрізок невидимий при (tmaxmin) <t <(tminmax). Остання вимога є простим наслідком з класичної задачі лінійного програмування.

Рішення на кордоні a = 0 виникає у разі протикання (об'єктів).

Один із прийомів полягає в запам'ятовуванні всіх точок протикання й у додаванні до сцени відрізків, що пов'язують ці точки. Відрізки утворюються шляхом з'єднання кожної точки протикання пари тіл, пов'язаних ставленням протикає, з усіма іншими точками протикання для цієї пари об'єктів. Потім перевіряється екранування цих відрізків даними тілами. Видимі відрізки утворюють структуру протикання.

З практики відомо, що рішення задовольняють нерівностям hj> 0, можуть існувати і за межами області, обмеженою умовами 0 £ t £ 1 і a = 0. Тому три рівняння, що описують ці межі, тобто t = 0, t - 1 = 0 і a = 0, потрібно додати до безлічі рівнянь hj = 0. Теперьчісло рішень одно (j + 2) (j + 3) / 2, де j - кількість площин, що обмежують опуклий об'єм тіла.

Як згадувалося раніше, вибір максимального з мінімального і мінімального з максимальних значень t серед можливих коректних рішень зазначеної системи рівнянь є простим завданням лінійного програмування. Її вирішення еквівалентно визначенню коректною обмеженій області, що виходить в результаті графічного рішення. Передбачається, що цей алгоритм використовується тільки для таких відрізків, про які відомо, що вони частково або повністю невидимі. Всі нелицьові і все повністю видимі відрізки виявлені і видалені до початку роботи алгоритму. Алгоритм починає роботу з такими значеннями t і a, які є рішеннями пари лінійних рівнянь з номерами е1 і е2, а також з tmin і tmax (поточними мінімальним і максимальним значеннями t) і з n (потужністю безлічі рівнянь). На першому етапі алгоритму перевіряється виконання умов hj> 0. Якщо ці умови виконані, то на другому етапі обчислюються значення tmin і tmax. Результатом є значення tmaxmin і tminmax.

Метод рішення, обговорювався вище, вимагає великих витрат машинного часу. Тому варто пошукати більш швидкі способи визначення повністю видимих ​​відрізків. Основна: ідея полягає у встановленні того факту, що обидва кінці відрізка лежать між точкою спостереження та який-небудь видимої площиною. Оскільки

u = s + t d + a g

При a = 0 значення u задає сам відрізок. Далі, якщо a = 0, при t = 0 і t = 1 виходять кінцеві точки відрізка. Також відомо, що

hj = u * [VT] = pj + qjt + wja

і зауважимо, що при t = 0 pj є скалярним добутком кінцевий точки відрізка і j-й площині, яка обмежує тіло. Аналогічно pj + qj є скалярним добутком інший кінцевий точки відрізка і j-й площині, яка обмежує тіло. Нарешті, нагадаємо, що j-я площину, що обмежує тіло, видимою, якщо wj = 0. Тому, якщо wj £ О і pj £ 0, то один кінець відрізка лежить чи видимої площині або між видимою площиною і точкою спостереження. Якщо ж pj + qj £ 0, то інший кінець відрізка також лежить або на видимій площині, або між цією площиною і точкою спостереження. Отже, відрізок повністю бачимо, для будь-якого j

wj £ О і pj £ 0 і pj + qj £ 0.

Ці умови гарантують, що нерівності hj £ 0 не можуть бути виконані ні за яких a ³ 0 і 0 £ t £ 1. Тому ніяка частина відрізка може бути невидимою, тобто відрізок повністю бачимо.

Нижче наводиться ефективна реалізація алгоритму Робертса. Цей алгоритм ділиться на три етапи. На першому етапі кожне тіло аналізується індивідуально з метою видалення нелицьових площин. На другому етапі перевіряється екранування залишився кожному тілі ребер іншими тілами з метою виявлення їх невидимої відрізків. На третьому етапі обчислюються відрізки, що утворюють нові ребра при протиканні тілами один одного. У даному алгоритмі передбачається, що тіла складаються з плоских полігональних граней, які в свою чергу складаються з ребер, а ребра - з окремих вершин. Усі вершини, ребра та грані пов'язані з конкретним тілом.

Видалення нелицьових площин

Для кожного тіла в сцені:

Сформувати багатокутники граней і ребра, виходячи зі списку вершин тіла.

Обчислити рівняння площини для кожної полигональной межі тіла.

Перевірити знак рівняння площини:

Взяти будь-яку точку всередині тіла, наприклад усереднивши координати його вершин.

Обчислити скалярний твір рівняння площини і точки всередині тіла.

Якщо це скалярний твір <О, то змінити знак рівняння цієї площини.

Сформувати матрицю тіла.

Помножити її зліва на матрицю, зворотну матриці видового перетворення, що включає перспективу.

Обчислити і запам'ятати габарити прямокутної осяжний оболонки перетвореного обсягу: xmin, xmax, ymin, ymax.

Визначити нелицьові площині:

Обчислити скалярний твір пробної точки, що у нескінченності, на перетворену матрицю тіла.

Якщо це скалярний твір <О, то площина невидима.

Видалити весь багатокутник, що лежить у цій площині. Це позбавляє від необхідності окремо розглядати, невидимі лінії, утворені перетином пар невидимих ​​площин.

Видалення з кожного тіла тих ребер, які екрануються усіма іншими тілами в сцені:

Якщо задано тільки одне тіло, то алгоритм завершується.

Сформувати пріоритетний список цих тіл:

Провести сортування по z. Сортування проводиться за максимальним значенням координати z вершин перетворених тел. Першим в упорядкованому списку і які мають найбільшим пріоритетом буде тіло, яка має мінімальне серед максимальних значень z. У використовуваної правої системі координат це тіло буде самим віддаленим від точки спостереження, що у нескінченності на осі z.

Для кожного тіла з пріоритетного списку:

Перевірити екранування всіх лицьових ребер іншими тілами сцени. Тіло, ребра якого перевіряються, називається пробним об'єктом, а тіло, щодо якого зараз проводиться перевірка, називається пробним тілом. Природно, що потрібно перевіряти екранування пробного об'єкта лише з тими пробними тілами, які мають нижче пріоритети.

Провести перевірки екранування для прямокутних осяжний оболонок пробного об'єкта та пробного тіла:

Есліxmin (пробне тіло)> xmax (Пробний об'єкт) або

xmax (Пробне тіло) <xmin (Пробний об'єкт) або

ymin (пробне тіло)> ymax (Пробний об'єкт) або

ymax (пробне тіло) <ymin (Пробний об'єкт),

то пробне тіло не може екранувати жодного ребра пробного об'єкта. Перейти до наступного пробного тілу. В іншому випадку:

Провести попередні перевірки протикає, щоб побачити, не проштрикується чи пробне тіло пробним об'єктом і чи існує можливість часткового екранізування першого останнім.

Порівняти максимальне значення z у пробного об'єкту з мінімальним значенням z у пробного тіла.

Якщо zmax (Пробний об'єкт) <zmin (пробне тіло), то протикання неможливо. Перейти до чого тілу. В іншому випадку:

Перевірити видиме протикання.

Якщо zmin (Пробний об'єкт)> zmax (пробне тіло), то пробний об'єкт може проткнути передню грань пробного тіла.

Встановити прапор видимого протикання для подальшого використання. Занести простромили тіло в список протикання.

Якщо xmax (Пробне тіло)> xmin (Пробний об'єкт) або

xmin (пробне тіло) <xmax (Пробний об'єкт),

то пробний об'єкт може проткнути бік пробного тіла.

Встановити прапор видимого протикання для подальшого використання. Завести тіло в список протикання.

Якщо ymax (пробне тіло)> ymin (Пробний об'єкт) або

ymin (пробне тіло) <ymax (Пробний об'єкт),

то пробний об'єкт може проткнути верх або віз пробного тіла.

Встановити прапор видимого протикання для подальшого використання. Занести простромили тіло в список протикання.

Якщо список протикання порожній, то встановлювати прапор протикання не треба.

Провести перевірки екранування ребер:

Обчислити s і d для ребра.

Ви числити p, q, w для кожної площини, що несе грань пробного тіла.

Перевірка повної видимості. Якщо ребро повністю, мабуть, то перейти до наступного ребру.

Сформувати рівняння hj = 0 і вирішити їх, об'єднуючи попарно і включивши в систему рівняння кордонів t = 0 і t = 1. Якщо встановлений прапор видимого протикає, то систему треба включити і рівняння кордону a = 0. Запам'ятати точки протикання. В іншому випадку кордон a = 0 не враховувати.

Для кожної пари (t, a), що є рішенням перевірити виконання умов 0 £ t £ 1, a ³ 0 і hj> 0 для всіх інших площин. Якщо ці умови виконані, то знайти tmaxmin і tminmax.

Обчислити видимі ділянки відрізків і зберегти їх для подальшої перевірки екранування тілами з низькими пріоритетами.

Визначити видимі відрізки, пов'язують точки протикання:

Якщо прапор видимого протикання не встановлено, перейти до процедури візуалізації.

Якщо точок протикання не виявлено, перейти до процедури візуалізації.

Сформувати всі можливі ребра, що з'єднують точки протикає, для пар тіл, пов'язаних ставленням протикання.

Перевірити екранування всіх з'єднують ребер обома тілами, пов'язаними ставленням протикання.

Перевірити екранування решти що з'єднують ребер іншими тілами сцени. Запам'ятати видимі відрізки.

Візуалізувати решта видимі відрізки ребер.

Алгоритм використовує Z-буфер

Це один з найпростіших алгоритмів видалення невидимих ​​поверхонь. Працює цей алгоритм у просторі зображення. Ідея z-буфера є простим узагальненням ідеї про буфері кадру. Буфер кадру використовується для запам'ятовування атрибутів (інтенсивності) кожного пікселя в просторі зображення. Z-буфер - це окремий буфер глибини, використовуваний для запам'ятовування координати z або глибини кожного видимого піксела в просторі зображення. У процесі роботи глибина або значення z кожного нового пікселя, який потрібно занести в буфер кадру, порівнюється з глибиною того пікселя, який вже занесений в z-буфер. Якщо це порівняння показує, що новий піксел розташований попереду піксела, що знаходиться в буфері кадру, то новий піксел заноситься в цей буфер і, крім того, проводиться корегування z-буфера новим значенням z. Якщо ж порівняння дає протилежний результат, то ніяких дій не проводиться. По суті, алгоритм є пошуком по x та y найбільшого значення функції z (z, y).

Головна перевага алгоритму - його простота. Крім того, цей алгоритм вирішує завдання про видалення невидимих ​​поверхонь і робить тривіальної візуалізацію перетинань складних поверхонь. Сцени можуть бути будь-якої складності. Оскільки габарити простору зображення фіксовані, оцінка обчислювальної трудомісткості алгоритму не більш ніж лінійна. Оскільки елементи сцени чи картинки можна заносити в буфер кадру або в z-буфер в довільному порядку, їх не потрібно попередньо сортувати за пріоритетністю глибини. Тому це економить обчислювальний час, що витрачається на сортування по глибині.

Основний недолік алгоритму - великий обсяг необхідної пам'яті. Якщо сцена піддається видовому перетворенню і відсікається до фіксованого діапазону координат z значень, то можна використовувати z-буфер з фіксованою точністю. Інформацію про глибину потрібно обробляти з більшою точністю, ніж координатну інформацію на площині (x, y); зазвичай буває достатньо 20 біт. Буфер кадру розміром 512х512х24 біт в комбінації з z-буфером розміром 512х512х20 біт вимагає майже 1.5 мегабайт пам'яті. Однак зниження цін на пам'ять робить економічно виправданим створення спеціалізованих запам'ятовуючих пристроїв для z-буфера і що з ним апаратури.

Альтернативою створенню спеціальної пам'яті для z-буфера є використання для цієї мети оперативної або масової пам'яті. Зменшення необхідної пам'яті досягається розбивкою простору зображення на 4, 16 або більше квадратів або смуг. У граничному варіанті можна використовувати z-буфер розміром в один рядок розгортки. Для останнього випадку є цікавий алгоритм порядкового сканування. Оскільки кожен елемент сцени обробляється багато разів, то сегментування z-буфера, взагалі кажучи, призводить до збільшення часу, необхідного для обробки сцени. Проте сортування на площині, що дозволяє не обробляти всі багатокутники в кожному з квадратів чи смуг, може значно скоротити це зростання.

Інший недолік алгоритму z-буфера полягає в трудомісткості і високої вартості усунення сходового ефекту, а також реалізації ефектів прозорості і просвічування.

Більш формальний опис алгоритму z-буфера таке:

Заповнити буфер кадру фоновим значенням інтенсивності та кольору.

Заповнити z-буфер мінімальним значенням z.

Перетворити кожен багатокутник в растрову форму в довільному порядку.

Для кожного Піксель (x, y) у багатокутнику обчислити його глибину z (x, y).

Порівняти глибину z (x, y) зі значенням Z буфер (x, y), що зберігаються в z-буфері в цій же позиції.

Якщо z (x, y)> z буфер (x, y), то записати атрибут цього багатокутника (інтенсивність, колір і т. п.) в буфер кадру і замінити z-буфер (x, y) на z (x, y).

В іншому випадку ніяких дій не виробляти.

В якості попереднього кроку там, де це доцільно, застосовується видалення нелицьових граней.

Якщо відомо рівняння площини, що несе кожен багатокутник, то обчислення глибини кожного пікселя на скануючої рядку можна проробити покроковим способом. Як відомо рівняння площини має вигляд

ax + by + cz + d = 0

z = - (ax + by + d) / c ¹ 0

Для сканує рядки y = const. Тому глибина піксела наетом рядку, у якого x = x + D x, дорівнює

z1 - z = - (ax1 + d) / c + (ax + d) / c = a (x - x1) / c

або

z1 = z - (a / c) D x

Але D x = 1, тому z1 = - (а / с).

Алгоритм, який використовує z-буфер, можна також застосувати для побудови перерізів поверхонь. Зміниться тільки оператор порівняння:

z (x, y)> z-буфер (x, y) and z (x, y) £ Zсеченія

де Zсеченія - глибина шуканого перетину. Ефект полягає в тому, що залишаються лише елементи поверхні, які лежать на самому перетині або позаду нього.

Алгоритм визначення видимих ​​поверхонь шляхом трасування променів

Оцінки ефективності всіх алгоритмів видалення невидимих ​​поверхонь, викладених раніше, залежать від певних характеристик когерентності тієї сцени, на якій ведеться пошук її видимих ​​ділянок. На відміну від нього трасування променів є методом грубої сили. Головна ідея, що лежить в основі цього методу, полягає в тому, що спостерігач бачить будь-який об'єкт у вигляді испускаемого якимось джерелом світла, який падає на цей об'єкт і потім якимось шляхом доходить до спостерігача. Світло може досягти спостерігача, відбившись від поверхні, поламав або пройшовши через неї. Якщо простежити за променями світла, випущеними джерелом, то можна переконатися, що дуже мало хто з них дійдуть до спостерігача. Отже, цей процес був би обчислювально неефективний. У наслідку цього було запропоновано відстежувати (трасувати) промені у зворотному напрямку, тобто від спостерігача до об'єкта, як показано на рис. 3.11. У першому алгоритмі трасування припинялася, як тільки промінь перетинав поверхню видимого непрозорого об'єкта; тобто промінь використовувався тільки для обробки прихованих або видимих ​​поверхонь. З плином часу був реалізований алгоритм трасування променів з допомогою загальних моделей освітлення. Ці алгоритми враховують ефекти відображення одного об'єкта від поверхні іншого, заломлення, прозорості і затінення. Проводиться також усунення ступенчатости. Розглянемо застосуванням методу трасування променів для визначення видимих ​​або прихованих поверхонь.

3.11. Проста трасування променів

Рис.3.11 служить ілюстрацією алгоритму трасування променів. У цьому алгоритмі передбачається, що сцена вже перетворена в простір зображення. Перспективне перетворення немає. Вважається, що точка зору або спостерігач знаходиться в нескінченності на позитивній півосі z. Тому всі світлові промені паралельні осі z. Кожен промінь, що виходить від спостерігача, проходить через центр піксела на растрі до сцени. Траєкторія кожного променя відстежується, щоб визначити, які саме об'єкти сцени, якщо такі існують, перетинаються з цим променем. Необхідно перевірити те що кожного об'єкта сцени з кожним променем.

3.12. Трасування променя з урахуванням перспективи

Якщо промінь перетинає об'єкт, то визначаються різноманітні точки перетину променя і об'єкта. Можна отримати велику кількість перетинів, якщо розглядати багато об'єктів. Ці перетину упорядковуються по глибині. Перетин з максимальним значенням z представляє видиму поверхню для даного пікселя. Атрибути цього об'єкта використовуються для визначення характеристик піксела.

Якщо точка зору знаходиться не в нескінченності, алгоритм трасування променів лише трохи ускладнюється. Тут передбачається, що спостерігач як і раніше знаходиться на позитивній півосі z. Картинна площину, тобто растр, перпендикулярна осі z, як показано на рис 3.12. Завдання полягає в тому, щоб побудувати одноточечную центральну проекцію на картинну площину.

Найбільш важливим елементом алгоритму визначення видимих ​​поверхонь шляхом трасування променів, є процедура визначення перетинів. До складу сцени можна включати будь-який об'єкт, для якого можна створити процедуру побудови перетинів. Об'єкти сцени можуть складатися з набору плоских багатокутників, багатогранників або тіл, обмежених чи визначених квадратичними або біполіноміальнимі параметричними поверхнями. Оскільки 75-95% часу, що витрачається алгоритмом трасування променів, забирають визначення перетинів, то ефективність процедури пошуку перетинань надає значно вплив на продуктивність всього алгоритму. Обчислювальна вартість визначення перетинів довільної просторової прямий (променя) з одним виділеним об'єктом може виявитися високою. Щоб позбутися непотрібного пошуку перетинань, проводиться перевірка перетину променя з об'ємною оболонкою аналізованого об'єкта. І якщо промінь не перетинає оболонки, то не потрібно більше шукати перетинань цього об'єкта з променем. Як оболонки можна використовувати прямокутний паралелепіпед чи сферу.

3.13 Сферична і прямокутна оболонки

Хоча, як показано, на рис. 3.13, використання сфери в якості оболонки може бути неефективним, факт перетину тривимірного променя зі сферою визначається дуже просто. Зокрема, якщо відстань від центру сферичної оболонки до променя перевершує радіус цієї сфери, промінь не перетинає оболонки. Отже, він не може перетинатися і з об'єктом.

Тому тест зі сферичною оболонкою зводиться до визначення відстані від точки до тривимірної прямої, тобто променя. Будемо використовувати параметричне представлення прямої, що проходить через точки P1 (x1, y1, z1) і P2 (x2, y2, z2) тобто:

Р (t) = P1 + (P2 - P1) t

з компонентами

x = x1 + (x2 - x1) t = x1 + at

y = y1 + (y2 - y1) t = y1 + bt

z = z1 + (z2 - z1) t = z1 + ct

Тоді мінімальна відстань d від цієї прямої до точки P0 (x0, y0, z0) дорівнює:

d2 = (x - x0) 2 + (y - y0) 2 + (z - z0) 2

а параметр t, що визначає найближчу точку Р (t) дорівнює:

Якщо d2 > R2, де R - радіус сферичної оболонки, то промінь не може перетнутися з об'єктом.

Виконання габаритного тесту з прямокутною оболонкою в тривимірному просторі вимагає великого обсягу обчислень. При цьому слід перевірити те променя щонайменше з трьома нескінченними площинами, обмежують прямокутну оболонку. Оскільки точки перетину можуть опинитися поза граней цього паралелепіпеда, то для кожної з них випливає, крім того, зробити перевірку на охоплення чи потрапляння всередину. Отже, для трьох вимірів дослідження з прямокутною оболонкою виявляється повільнішим, ніж тест зі сферичною оболонкою.

Однією простою процедурою можна звести дослідження з прямокутною оболонкою до порівняння знаків, спрощуючи тим самим обчислення перетинів з об'єктом, а також порівняння за глибиною серед точок перетину. У цій процедурі використовуються перенесення повороти навколо координатних осей у тому, щоб домогтися збігу променя з віссю z. Аналогічним перетворенням піддається і прямокутна оболонка об'єкта. Промінь перетинає оболонку, якщо в новій перенесеної і поверненою системі координат знаки xmin і xmax, а так само ymin і ymax. протилежні, як показано на рис. 3.14.

3.14 Перетин прямокутної області у реформованій системі координат

Розглянемо спрощення обчислень точок перетину променя і поверхні другого порядку загального вигляду. У довільній декартовій системі координат поверхонь другого порядку є геометричним місцем точок, координати яких задовольняють рівняння:

Q (x, y, z) = a1x2 + a2y2 + a3z2 +

b1yz + b2xz + b3xy +

c1x + c2y + c3z + d = 0

Після застосування перетворення, що є комбінацією перенесення і повороту і використовується для поєднання променя з віссю z, те що цього променя з поверхнею, якщо воно має місце, виникає при x = y = 0. Тому в загальному випадку точки перетину є рішеннями рівняння:

тобто

де штрих зверху позначає коефіцієнти загального рівняння поверхні другого порядку після перетворення. Якщо , То рішення виражаються комплексними числами і промінь не перетинає поверхні. Якщо нескінченна поверхню другого порядку (наприклад, конус або циліндр) обмежена площинами, то ці площині слід перетворити і перевірити на перетину. Якщо знайдено те що з нескінченної обмежує площиною, то необхідно, крім того, зробити перевірку потрапити всередину. Однак у реформованій системі координат цю перевірку можна провести на двовимірної проекції фігури, утвореної перетином обмежує площини і квадратичної поверхні. Для отримання точки перетину у вихідній системі координат необхідно застосувати зворотне перетворення.

Обчислення перетинів для елементів біполіноміальних параметричних поверхонь складніші. Уіттед запропонував простий метод розбиття для елемента бікубічеськой поверхні. Обчислення виконуються з елементом поверхні в його початковому положенні. Якщо промінь перетинає сферичну оболонку елемента поверхні, то цей шматок розбивається з допомогою алгоритму розбивки запропонованого Кетмул. Потім промінь перевіряється на перетин зі сферичними оболонками піделементи. Якщо те що не виявлено, то промінь не перетинається і з самим елементом. Якщо ж промінь перетинається зі сферичною оболонкою якогось піделементи, то останній розбивається далі. Процес завершується, якщо жодна зі сферичних оболонок не пересічена або якщо досягнуть наперед визначений їх мінімальний розмір. Ці сферичні оболонки мінімальної відстані і є шуканими перетинами променя і елемента поверхні.

При реалізації перетворення, сполучає промінь з віссю z, метод розбивки можна використовувати скоріше стосовно прямокутним оболонок, ніж до сферичним. Це скорочує число розбиття і збільшує ефективність алгоритму. Для параметричних поверхонь, що мають властивість опуклої оболонки, наприклад для поверхонь Безьє і В-сплайнів, число розбиття можна скоротити додатково за рахунок ускладнення алгоритму, для піделементи скористатися їх опуклими оболонками замість прямокутних.

Кадзия розробив метод для біполіноміальних параметричних поверхонь, який не вимагає їх підрозділи. Цей метод заснований на поняттях, запозичених із алгебраїчній геометрії. Рішення які утворюються при цьому алгебраїчних рівнянь вищих ступенів перебувають чисельно. Метод, подібний цьому, можна реалізувати у реформованій системі координат. Нагадаємо, що біполіноміальная параметрична поверхня визначається рівнянням

Q (u, w) = 0

з компонентами

x = f (u, w)

y = g (u, w)

z = h (u, w)

у реформованій системі координат виконана умова x = y = 0. Значить,

f (u, w) = 0

g (u, w) = 0

Спільне рішення цієї пари рівнянь дає значення u і w для точок перетину. Підстановка цих значень в рівняння z = h (u, w) дає компоненту z для точок перетину. Невдача спроби знайти дійсне рішення означає, що промінь не перетинає поверхню. Ступінь системи рівнянь для u, w дорівнює добутку ступенів біполіноміальних поверхонь. Бікубічна поверхню, наприклад, має шосту ступінь. Отже, у випадку знадобляться чисельні методи рішення. Там, де це припустимо, для початкового наближення u і w можна використовувати перетину променя з опуклою оболонкою. Для отримання перетинань у вихідній системі координат, як і раніше, слід використовувати зворотне перетворення.

Якщо трассируемого промінь перетинає об'єкти сцени у кількох точках, то необхідно визначити видиме те. Для алгоритмів визначення видимості простих непрозорих поверхонь перетином з видимою поверхнею буде точка з максимальним значенням координати z. Для більш складних алгоритмів, що враховують відображення і заломлення, ці перетину слід упорядкувати уздовж променя по відстані від його початку. У реформованій системі координат цього можна досягнути простий сортуванням по z.

Алгоритм трасування променів для простих непрозорих поверхонь можна представити наступним чином:

Підготовка даних для сцени:

Створити список об'єктів, у якому щонайменше наступну інформацію:

Повний опис об'єкта: тип, поверхня, характеристики і т. п.

Опис сферичної оболонки: центр і радіус,

Прапор прямокутної оболонки. Якщо цей прапор піднято, то буде виконано габаритний тест з прямокутною оболонкою, якщо він опушен, то тест виконуватися не буде. Зауважимо, що габаритний тест необхідний для всіх об'єктів, наприклад у сфері він не потрібен.

Опис прямокутної оболонки: xmin, xmax, ymin, ymax, zmin, zmax.

Для кожного трассируемого променя:

Виконати для кожного об'єкта тривимірний тест зі сферичною оболонкою у вихідній системі координат. Якщо промінь перетинає цю сферу, то занести об'єкт в список активних об'єктів. Якщо список активних об'єктів порожній, то зобразити даний піксел з фоновим значенням інтенсивності і продовжувати роботу. В іншому випадку, перенести повернути промінь так, щоб він совместился з віссю z. Запам'ятати це комбіноване перетворення.

Для кожного об'єкта зі списку активних об'єктів:

Якщо прапор прямокутної оболонки піднято, перетворити, використовуючи комбіноване перетворення, цю оболонку до системи координат, в якій знаходиться луч1 і відповідний тест. Якщо перетину з променем немає, то перейти до наступного об'єкта. Інакше перетворити, використовуючи комбіноване перетворення, об'єкт до системи координат, в якій перебуває промінь, і визначити його перетину з променем, якщо вони існують. Занести всі перетину в список перетинів.

Якщо список перетинань порожній, то зобразити даний піксел з фоновим значенням інтенсивності.

В іншому випадку визначити z для списку перетинів.

Обчислити перетворення, зворотне комбінованому перетворенню.

Використовуючи це зворотне перетворення, визначити точку перетину у вихідній системі координат.

Зобразити даний піксел, використовуючи атрибути пересеченного об'єкту і відповідну модель освітленості.

Зауважимо, що алгоритм визначення видимості простих непрозорих поверхонь, не вимагає обраховувати перетворення, зворотне комбінованому, чи визначати точку перетину у вихідній системі координат, тоді як моделі висвітлення не виникає необхідність включення до алгоритму властивостей поверхні об'єкта чи її орієнтації в точці перетину. Ці кроки включені в даний алгоритм для повноти і зручності при реалізації алгоритму трасування променів з урахуванням загальної моделі освітленості.

Дві модифікації цього простого алгоритму помітно підвищують його ефективність. Перша модифікація полягає в понятті кластерних груп просторово зв'язаних об'єктів. Наприклад, припустимо, що сцена складається зі стола, на якому стоять ваза з фруктами і блюдо з цукерками. У вазі лежать апельсин, яблуко, банан і груша. Страва містить кілька цукерок різних форм і кольорів. Вводяться сферичні оболонки для груп або кластерів пов'язаних об'єктів, наприклад для вази і всіх плодів у ній, для страви і всіх цукерок у ньому, а також для столу і всіх предметів у ньому. Сферичні оболонки, що охоплюють більше ніж один об'єкт, називаються сферичними кластерами. Якщо це необхідно, то можна ввести і прямокутні кластери Запроваджується, крім того, найбільший сферичний кластер, що його сферою сцени, яка охоплює всі об'єкти в цій сцені. Потім сферичні оболонки обробляються в ієрархічному порядку. Якщо промінь не перетинає сферу сцени, то він не може перетнути і жодного з його об'єктів. Отже, піксел, що відповідає цьому променю, буде зображений з фоновим значенням інтенсивності. Якщо ж промінь перетинає сферу сцени, то, на те з променем перевіряються сферичні кластери і сферичні оболонки об'єктів, не що є в одному з сферичних кластерів, що належать кластеру сцени. Якщо промінь не перетинає сферичний кластер, то саме цей кластер і всі об'єкти або кластери, що містяться в ньому, виключаються з подальшого розгляду. Якщо чи ж промінь перетинає кластер, то ця процедура рекурсивно повторюється до тих пір, поки не будуть розглянуті всі об'єкти. Якщо промінь перетинає сферичну оболонку якогось об'єкта в якій-небудь точці, то цей об'єкт заноситься до списку активних об'єктів. Ця процедура значно скорочує кількість обчислень точок перетину променя зі сферичними оболонками і тим самим підвищує ефективність всього алгоритму.

Друга модифікація використовує впорядкування по пріоритет щоб скоротити число об'єктів, для яких обчислюються перетину з променем. Замість того, щоб негайно проводити обчислення перетину об'єкта до променем, як це робиться у викладеному вище простому алгоритмі, об'єкт міститься в список перетнув об'єктів. Після розгляду всіх об'єктів сцени перетворений список перетнув об'єктів впорядковується за пріоритетом глибини. Для визначення пріоритетного порядку можна використовувати центри сферичних оболонок або найбільші (найменші) значення z прямокутних оболонок. Перетину променя з об'єктами зі списку перетнув об'єктів визначаються в порядку їх пріоритетів. На жаль точка перетину променя з першим з об'єктів в упорядкованому з пріоритетів списку перетнув об'єктів необов'язково буде видимою. Необхідно визначити точки перетину променя з усіма потенційно видимими об'єктами з багатьох {Q} і занести їх до списку перетинів. Потім модифікований алгоритм впорядковує цей список перетинань так, як це робилося і в простому алгоритмі. На щастя, безліч {Q} потенційно видимих ​​об'єктів зазвичай значно менше ніж об'єктів у списку перетнув променем. Отже, ефективність алгоритму зросте. Обидві ці модифікації застосовні також і до загального алгоритму трасування променів, що враховує відображення, заломлення і прозорість.

Викладений вище простий алгоритм не використовує тієї обставини, що деякі грані багатогранника є нелицьових і їх можна відразу видалити, не враховується тут і можлива когерентність сцени. Наприклад, несуттєвий порядок обробки пікселів. Разом з тим розгляд цих пікселів в порядку сканування рядки розгорнення дозволило б скористатися в алгоритмі когерентністю скануючих рядків. Інший підхід може полягати в підрозділі сцени, причому облік когерентності областей привела б до зменшення числа об'єктів, що розглядаються для кожного променя і, отже, до підвищення ефективності алгоритму. Хоча використання подібних прийомів підвищує ефективність алгоритму визначення видимості непрозорих поверхонь їх застосувати загалом алгоритмі трасування променів, що враховує відображення, заломлення і прозорість. Наприклад, якщо в алгоритмі враховано відбиток, то об'єкт, який повністю закритий іншим об'єктом, може бути видимим, як відображення від третього об'єкта. Оскільки метод трасування променів є метолом грубої сили, алгоритми визначення видимості непрозорих поверхонь, що обговорювалися раніше, є більш ефективними.

Д. Рот зазначив, що алгоритм трасування променів можна використовувати також і для створення каркасних креслень суцільних тіл. При цьому передбачається, що промені народжуються в тому порядку, в якому відбувається сканування екрана, тобто зверху вниз і зліва направо. Получающаяся процедура така:

Якщо видима поверхня для Пиксел (x, y) відповідає фону або відрізняється від видимої поверхні для Пиксел (x - 1, y) або для Пиксел (x, y - 1), то зобразити цей піксель. В іншому випадку піксел не зображати.

Алгоритм трасування променів можна використовувати, крім того, для визначення фізичних властивостей суцільного тіла. Повне розгляд цього питання не входить в цю роботу. Однак для ілюстрації цього підходу наведемо один приклад. Зокрема, обсяг будь-якого суцільного тіла можна визначити, аппроксимируя його сумою маленьких прямокутних паралелепіпедів. Це можна зробити, породивши безліч паралельних променів, розташованих на певних відстанях один від одного. Точки перетину кожного променя із заданим обсягом обчислюються і впорядковуються вздовж напрямку цього променя. Якщо піддати промінь переносу, що сполучає його з віссю z, як це було описано вище, то обсяг кожного прямокутного паралелепіпеда буде дорівнює:

де lx і ly - відстань між променями по горизонталі й вертикалі відповідно. Кожне складова (zi-1 - zi) являє собою ділянку променя, внутрішній заданого тіла. Обсяг тіла, отже, дорівнює сумі обсягів усіх таких прямокутних паралелепіпедів. Точність результатів залежить від кількості використаних променів. Точність можна підвищити, помірно збільшивши обсяг обчислень і рекурсивно зменшивши розмір "пікселя", в тому випадку, якщо обсяги суміжних прямокутних паралелепіпедів відрізняються більш ніж на заздалегідь задану величину. При такому підході точніше визначаються обсяги тих елементів тіла, де мають місце швидкі зміни, наприклад, у околицях ребер тіл, обмежених криволінійними поверхнями.

Зважаючи на внутрішньо властивою алгоритму трасування променів паралельності обчислень (тут всі промені обробляються однаково незалежно один від одного) його можна реалізувати апаратно на основі інтегральних схем з використанням методів паралельної обробки.

Резюме

У цій роботі детально обговорювалося декілька основних алгоритмів, використовуваних для виконання завдання видалення невидимих ​​ліній або поверхонь. Однак це далеко не все, що є. Крім вище сказаного можна назвати алгоритм видалення невидимих ​​ліній запропонований Хеджли, який заснований на використанні списку пріоритетів, розбиття та порядкового сканування. Цей алгоритм працює у просторі об'єкта, отримує на вході опуклі або неопуклі багатокутники, а оцінка його ефективності лінійно залежить від кількості об'єктів.

Іншим прикладом є запропонований Азертоном інтервальний алгоритм порядкового сканування, який використовується для візуалізації сцен, які утворюються в системі конструктивного моделювання суцільних тіл. Внутрішній цикл цього алгоритму змінено так, щоб можна було реалізувати одномірні теоретико-множинні операції, необхідні для моделюючої системи, яка користується алгоритмом трасування променів. Азертон вказує, що цей інтервальний алгоритм порядкового сканування вимагає приблизно в 60 разів менше часу, ніж звичайний алгоритм трасування променів.

У висновку хочу сказати, що комп'ютерна графіка не стоїть на місці. Вже давно існують численні програмні і апаратні реалізації алгоритмів побудови зображення. На ринку достатньо широко представлені різноманітні графічні акселератори і масиви швидкої пам'яті. Провідні виробники електронних компонентів підтримують обробку зображення на рівні процесорної техніки (MMX - Intel, 3D Now - AMD), отже, стає можливим реалізація "повільних", але дають кращу якість зображення алгоритмів. Окремо слід сказати таке явища, як віртуальна реальність, яка вже в даний час набуває широкого поширення. Одним словом, комп'ютерна графіка буде розвиватися до того часу - поки буде розвиватися і вдосконалюватися комп'ютерна техніка.